记录编号	360329	评测结果	AAAAAAAAAA
题目名称	[USACO Dec16]进击的三角形	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.745 s
提交时间	2016-12-29 12:45:08	内存使用	2.13 MiB

#include<cstdio>
#include<algorithm>
using namespace std; 
typedef long long ll;
const int N=310;
struct pt{
	ll x,y;
	pt(ll X=0,ll Y=0){x=X;y=Y;}
	pt operator - (const pt a)const{return pt(x-a.x,y-a.y);}
	ll operator ^ (const pt a)const{return x*a.y-a.x*y;}
}p[N],f[N][N];
int n,ans[N],Bel[N],Bet[N][N];
ll abs(ll x){return x>0?x:-x;}
//p[x]在p[y]下方，返回1 
bool bel(int x,int y){return p[x].x==p[y].x&&p[x].y<p[y].y;}
bool bet(int x,int y,int z){//p[z]在[p[x],p[y]]下方，返回1 
	if (p[x].x<p[y].x) swap(x,y);
	return p[z].x<p[x].x&&p[z].x>p[y].x&&(f[x][z]^f[y][z])>0;
}
int main()
{
	freopen("triangles.in","r",stdin);
	freopen("triangles.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%lld%lld",&p[i].x,&p[i].y);
	for (int i=1;i<=n;++i)
	for (int j=1;j<=n;++j)
		f[i][j]=p[i]-p[j];
	for (int i=1;i<=n;i++)
	for (int j=i+1;j<=n;j++){
		for (int k=1;k<=n;k++)
			Bet[i][j]+=bet(i,j,k);
		Bet[j][i]=Bet[i][j];
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
		Bel[i]+=bel(j,i);
	for (int i=1;i<=n;i++)
	for (int j=i+1;j<=n;j++)
	for (int k=j+1;k<=n;k++){
		int cnt,x=i,y=j,z=k;
		if (p[x].x>p[y].x||bel(x,y)) swap(x,y);
		if (p[x].x>p[z].x) swap(x,z);
		if (p[z].x<p[y].x||bel(z,y)) swap(y,z);
		cnt=Bet[x][z]-Bet[x][y]-Bet[y][z];
		if (!bel(y,x)&&!bel(y,z)){
			if (bet(x,z,y)) cnt=cnt-Bel[y]-1;
				else cnt=-cnt+Bel[y];
		}
		ans[cnt]++;
	}
	for (int i=0;i<=n-3;i++) printf("%d\n",ans[i]);
	return 0;
}