比赛 20110414 评测结果 AAAAAAAAAA
题目名称 数三角形 最终得分 100
用户昵称 .Xmz 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-04-14 10:57:05
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

const int maxn=100111;

struct point
{
	long long x,y;
}P[maxn],T[maxn];
int n;
long long ans;
void init()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	{
		scanf("%lld%lld",&P[i].x,&P[i].y);
	}
	ans=(long long)n*(long long)(n-1)*(long long)(n-2)/6;
}

bool cha(point &a,point &b)
{
	return (a.x*b.y-b.x*a.y<0);
}

void pointsort(int l,int r)
{
	if (l>=r) return ;
	int mid=(l+r)>>1,nowl=l,nowr=r;
	for (int i=l;i<=r;i++)
	if (i!=mid)
	{
		if (cha(P[i],P[mid])) T[nowl++]=P[i];
		else T[nowr--]=P[i];
	}
	T[nowl]=P[mid];
	for (int i=l;i<=r;i++) P[i]=T[i];
	pointsort(l,nowl-1);
	pointsort(nowl+1,r);
}

void solve()
{
	pointsort(0,n-1);
	int j=1;
	for (int i=0;i<n;i++)
	{
		while (cha(P[i],P[j])) j=(j+1>n-1) ? 0 : j+1;
		int t=(j+n-1-i)%n;
		ans-=t*(t-1)/2;
	}
	printf("%lld\n",ans);
}

int main()
{
	freopen("tricount.in","r",stdin);
	freopen("tricount.out","w",stdout);
	init();
	solve();
	return 0;
}