题意：给定平面上N（<=10^5）个整点，任意三点可以组成一个三角形，求把原点包含在内部的三角形个数。保证原点不在两点连线上。

我们反过来考虑，用总的三角形个数减去非法的三角形个数。

总的三角形个数是(N3)=N(N−1)(N−2)6；

然后考虑非法三角形的情况，原点在三角形外部。作原点和三个点的连线，我们会发现一定是形成一个锐角，所以答案只跟每个点的极角有关。

于是把每个点按照极角序排序，用单调队列维护一个半平面上的点，每次加入一个点时，删除队尾与该点成顺时针的点，此时对答案的贡献就是(M2)，M为队列中点的个数，最后加入这个点，具体实现见代码。

一些细节：把点按x坐标正负分成左右两部分，排序的时候就可以用叉积，单调队列扫的时候也用叉积判断。

代码：

#include 
     
      using namespace std;typedef long long ll;const int MAXN = 100005;struct P{ll x, y;}A[MAXN], B[MAXN], q[MAXN<<2];ll operator*(P a, P b){
    return a.x*b.y-a.y*b.x;} //叉积int cmp(P a, P b){
    return a*b<0;}int na, nb, N;int main(){    scanf("%d", &N);    for(int i=0; i
      
       0 || (p.x==0 && p.y>0)) A[na++]=p; //右半部分        else B[nb++]=p; //左半部分    }    sort(A, A+na, cmp); sort(B, B+nb, cmp);    int hd=0, tl=0;    for(int i=0; i