记录编号	246194	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Dec08] 巨大的围栏	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	5.895 s
提交时间	2016-04-05 16:38:57	内存使用	2.94 MiB

#include<cstdio>
#include<cmath>
#define ll long long
#define eps 1e-9
#define pi 3.14159265358979323846
inline int MAX(int A,int B){return A>B?A:B;}
int n,ans,num,b[260][260],c[260][260],q[260],f[260][260];
double a[260][260],rec[260][260];
bool vis[260][260];
int q1[260*260],q2[260*260],du[260][260];
struct point{int x,y;double z;}o[260];
inline double ABS(double X){return X<0?-X:X;}
inline double dis(int i,int j){
	return (o[i].x-o[j].x)*(o[i].x-o[j].x)+(o[i].y-o[j].y)*(o[i].y-o[j].y);
}
int main(){
	freopen("fence1.in","r",stdin);
	freopen("fence1.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d%d",&o[i].x,&o[i].y);
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
        if(i!=j){
			a[i][j]=atan2(o[j].y-o[i].y,o[j].x-o[i].x);
			if(a[i][j]<0)a[i][j]+=pi*2;
        }
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)rec[i][j]=dis(i,j);
	for(int i=1;i<=n;++i)
	    for(int j=1;j<=n;++j)
	        if(i!=j)for(int k=1;k<=n;++k){
				if(k!=i&&k!=j&&a[i][k]>a[i][j]&&(!b[i][j]||a[i][k]<a[i][b[i][j]]))b[i][j]=k;
				if(k!=j&&a[j][k]>a[i][j]-eps&&(!c[i][j]||a[j][k]<a[j][c[i][j]]-eps||
				(ABS(a[j][k]-a[j][c[i][j]])<eps&&rec[j][k]<rec[j][c[i][j]])))c[i][j]=k;
	        }
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)f[i][j]=-1;
	for(int i=1;i<=n;++i){
		int l=0,r=0;
		for(int j=1;j<=n;++j)f[i][j]=1,vis[i][j]=1,q1[++r]=i,q2[r]=j;
		while(l<r){
			int x=q1[++l],y=q2[l];
			if(b[x][y]){
				++du[x][b[x][y]];
				if(!vis[x][b[x][y]])
					q1[++r]=x,q2[r]=b[x][y],
					vis[x][b[x][y]]=1;
			}
			if(c[x][y]){
				++du[y][c[x][y]];
				if(!vis[y][c[x][y]])
					q1[++r]=y,q2[r]=c[x][y],
					vis[y][c[x][y]]=1;
			}
		}
		l=r=0;
		for(int j=1;j<=n;++j)if(!du[i][j])q1[++r]=i,q2[r]=j;
		while(l<r){
			int x=q1[++l],y=q2[l];
			if(b[x][y]){
				f[x][b[x][y]]=MAX(f[x][b[x][y]],f[x][y]);
				--du[x][b[x][y]];
				if(!du[x][b[x][y]])q1[++r]=x,q2[r]=b[x][y];
			}
			if(c[x][y]){
				f[y][c[x][y]]=MAX(f[y][c[x][y]],f[x][y]+1);
				--du[y][c[x][y]];
				if(!du[y][c[x][y]])q1[++r]=y,q2[r]=c[x][y];
			}
		}
		for(int j=1;j<=n;++j)ans=MAX(ans,f[j][i]);
		while(r)vis[q1[r]][q2[r]]=0,f[q1[r]][q2[r]]=-1,--r;
	}
	printf("%d",ans);
}