多校5 1004 HDU5784 统计锐角三角形数目

http://acm.hdu.edu.cn/showproblem.php?pid=5784

题意：n个点，找多少个锐角三角形数目

思路：极角排序+two pointers

当前选择的点集要倍增一倍，点集过大时，极角排序后，后面的点有可能和前面的点形成钝角

ans=总的三角形数目 - 三点共线的情况-直角和钝角

 // #pragma comment(linker, "/STACK:102c000000,102c000000")

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <sstream>

 #include <string>

 #include <algorithm>

 #include <list>

 #include <map>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <cstdlib>

 // #include <conio.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define inf 0x3f3f3f3f

 #define lson l,mid,rt<<1

 // #define rson mid+1,r,rt<<1|1

 const int N = ;

 const int M = 1e6+;

 const int MOD = 1e9+;

 #define LL long long

 #define LB long double

 // #define mi() (l+r)>>1

 double const pi = acos(-);

 const double eps = 1e-;

 void fre(){freopen("in.txt","r",stdin);}

 inline int read(){int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;}

 struct Point{

     LL x,y;

     Point(){}

     Point(LL _x,LL _y):x(_x),y(_y){}

     Point operator + (const Point &t)const{

         return Point(x+t.x,y+t.y);

     }

     Point operator - (const Point &t)const{

         return Point(x-t.x,y-t.y);

     }

     LL operator * (const Point &t)const{

         return x*t.y-y*t.x;

     }

     LL operator ^ (const Point &t)const{

         return x*t.x+y*t.y;

     }

     bool operator < (const Point &b)const{

         if (y * 1LL * b.y <= ) {

         if (y >  || b.y > ) return y < b.y;

         if (y ==  && b.y == ) return x < b.x;

         }

         return (*this)*b > ;

     }

 }p[N],v[N<<];

 int main(){

     int n;

     while(~scanf("%d",&n)){

         for(int i=;i<n;i++) scanf("%I64d%I64d",&p[i].x,&p[i].y);

         LL ans=1LL*n*(n-)*(n-)/,tem=;

         for(int k=;k<n;k++){

             int cnt=;

             for(int i=;i<n;i++){

                 if(k==i)continue;

                 v[cnt++]=p[i]-p[k];

             }

             sort(v,v+cnt);

             for(int i=;i<cnt;i++) v[i+cnt]=v[i];

             int cxt=;

             for(int i=;i<cnt;i++){

                 if(v[i-]*v[i]==&&(v[i-]^v[i])>) cxt++;

                 else cxt=;

                 tem+=cxt;

             }

             for(int i=,p1=,p2=;i<cnt;i++){

                 while(p1<=i||(p1<i+cnt&&v[p1]*v[i]<&&(v[p1]^v[i])>)) p1++;

                 while(p2<=i||(p2<i+cnt&&v[p2]*v[i]<)) p2++;

                 ans-=p2-p1;

             }

         }

         printf("%I64d\n",ans-tem/);

     }

     return ;

 }