[Elite 2010 U S Open Competition]求过原点的三角形数目、极角排序、维护

【题目大意】
给定N个二维平面上的点。
问他们取3个出来，过原点的三角形有多少个。
【算法分析】
先极角排序。
然后维护一个最长区间，使得区间中任意一个点对满足向量(O, i)和向量(O, j)的夹角【其它】
APIO最后一题的本质模型。
【CODE】
/*
ID:jie22221
TASK:tricount
LANG:C++
*/

#include #include #include #include using namespace std;
typedef long long lld;
const int N=100005;
int n;
struct Point{int x,y;}a[N];

void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
}

int get_xx(Point p){
if (p.x>=0 && p.y>0) return 1;
if (p.x>0 && p.y<=0) return 2;
if (p.x<=0 && p.y<0) return 3;
return 4;
}

int cj(Point p0,Point p1,Point p2){
lld res=(lld)(p1.x-p0.x)*(lld)(p2.y-p0.y)-(lld)(p1.y-p0.y)*(lld)(p2.x-p0.x);
if (res<0) return -1;
if (res==0) return 0;
return 1;
}

int cmp(const void *X,const void *Y){
Point x=*((Point*)X),y=*((Point*)Y);
int xx1=get_xx(x),xx2=get_xx(y);
if (xx1!=xx2) return xx1-xx2;
return cj(a[0],x,y);
}

void solve(){
lld ans=(lld)(n)*(n-1)*(n-2)/6,total;
int i,j=1;
for (i=1;i<=n;i++){
if (i==j) j=j%n+1;
while (i!=j%n+1 && cj(a[0],a[i],a[j%n+1])<0) j=j%n+1;
if (j else total=j-i;
ans-=total*(total-1)/2;
}
cout << ans << endl;
}

int main(){
freopen("tricount.in","r",stdin);
freopen("tricount.out","w",stdout);
input();
qsort(a+1,n,sizeof(Point),cmp);
solve();
}