【计算几何】【极角序】【二分】bzoj1914 [Usaco2010 OPen]Triangle Counting 数三角形

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
typedef double db;
#define N 100001
const db PI=acos(-1.0);
ll ans;
db jiao[N];
int n;
int main()
{
	db x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	  {
	  	scanf("%lf%lf",&x,&y);
	  	db t=atan2(y,x);
	  	jiao[i]=(t<0?t+2.0*PI:t);
	  }
	sort(jiao+1,jiao+n+1);
	for(int i=1;i<=n;++i)
	  if(jiao[i]<=PI)
	    {
	      int ef=upper_bound(jiao+1,jiao+n+1,jiao[i]+PI)-(jiao+i)-1;
	      ans+=(((ll)ef*(ll)(ef-1))>>1);
	    }
	  else
	    {
	      int ef=upper_bound(jiao+1,jiao+n+1,jiao[i]-PI)-(jiao+1);
	      ef+=(n-i);
	      ans+=(((ll)ef*(ll)(ef-1))>>1);
	    }
	printf("%lld\n",(ll)n*(ll)(n-1)*(ll)(n-2)/6-ans);
	return 0;
}