记录编号	370000	评测结果	AAAAAAAAAA
题目名称	[USACO Open10]数三角形	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.065 s
提交时间	2017-02-12 11:45:00	内存使用	4.87 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct pt{
	ll x,y;double angle;
	pt(ll X=0,ll Y=0){
		x=X;y=Y;
		angle=atan2(x,y);
	}
	ll operator ^ (const pt &a)const{return x*a.y-y*a.x;}
	bool operator < (const pt &a)const{return angle<a.angle;}
}p[N];
int n;
int main()
{
	freopen("tricount.in","r",stdin);
	freopen("tricount.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		p[i]=pt(x,y);
	}
	sort(p+1,p+n+1);
	for (int i=1;i<=n;i++) p[i+n]=p[i]; 
	int head=1,tail=0;
	ll ans=(ll)n*(n-1)*(n-2)/6;
	for (int i=1;i<=n;i++){
		for (;head<=tail&&p[head].angle<p[i].angle;head++);
		for (;tail<i+n-1&&(p[tail+1]^p[i])>=0;tail++);
		ans-=ll(tail-head)*(tail-head-1)/2;
	}
	printf("%lld\n",ans);
	return 0;
}