记录编号	168030	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Dec08] 巨大的围栏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.785 s
提交时间	2015-06-30 14:00:22	内存使用	1.34 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int SIZEN=310,INF=0x7fffffff/2;
class Point{
public:
	int x,y;
	Point(int _x=0,int _y=0){
		x=_x;
		y=_y;
	}
};
void print(const Point &p){
	cout<<"("<<p.x<<" "<<p.y<<")";
}
bool cmp_coor(const Point &a,const Point &b){
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
Point operator - (const Point &a,const Point &b){
	return Point(a.x-b.x,a.y-b.y);
}
int cross(const Point &a,const Point &b){
	return a.x*b.y-b.x*a.y;
}
int N;
Point P[SIZEN];
int from_scan[SIZEN][SIZEN]={0},to_scan[SIZEN][SIZEN]={0};
//直观地想象"一个引出扫描射线的转动枢轴......"例如机械式雷达的波束
void prepare(void){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			if(i==j) continue;
			//如果没有"三点不共线"的条件,这段可能有潜在问题
			int t1=0,t2=0;
			for(int k=1;k<=N;k++){
				if(k==i||k==j) continue;
				if(cross(P[j]-P[i],P[k]-P[i])>0){
					if(t1==0||cross(P[k]-P[i],P[t1]-P[i])>0) t1=k;
				}
				if(cross(P[j]-P[i],P[k]-P[j])>0){
					if(t2==0||cross(P[k]-P[j],P[t2]-P[j])>0) t2=k;
				}
			}
			from_scan[i][j]=t1;
			to_scan[i][j]=t2;
		}
	}
}
bool valid[SIZEN]={0};
int dp[SIZEN][SIZEN];
int del_step(const int &p1,int p2,int p3){//不选p3
	int x=from_scan[p2][p3];
	while(x&&!(valid[x]&&cross(P[p2]-P[p1],P[x]-P[p1])>0)){
		if(x==p3||x==p1) return 0;
		x=from_scan[p2][x];
	}
	if(!x||x==p3||x==p1) return 0;
	if(cross(P[p3]-P[p2],P[x]-P[p2])>0) return x;
	else return 0;
}
int sel_step(const int &p1,int p2,int p3){//选p3
	int x=to_scan[p2][p3];
	while(x&&!(valid[x]&&cross(P[p3]-P[p1],P[x]-P[p1])>0)){
		if(x==p3||x==p1) return 0;
		x=from_scan[p3][x];
	}
	if(!x||x==p3||x==p1) return 0;
	if(cross(P[p3]-P[p2],P[x]-P[p3])) return x;
	else return 0;
}
int DFS(const int &p1,int p2,int p3){//凸包起点p1,目前钦定了p2,待探查p3
	if(!p2||!p3) return -INF;
	//p1它其实是确定的......
	if(cross(P[p1]-P[p2],P[p3]-P[p2])>0) return -INF;
	int &ans=dp[p2][p3];
	if(ans!=-1) return ans;
	ans=1;//直接结束凸包
	ans=max(ans,DFS(p1,p3,sel_step(p1,p2,p3))+1);
	ans=max(ans,DFS(p1,p2,del_step(p1,p2,p3)));
	return ans;
}
int calc(int d){
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=N;i++) valid[i]=cmp_coor(P[d],P[i]);
	valid[0]=false;valid[d]=true;
	int ans=0;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			if(valid[i]&&valid[j]&&cross(P[i]-P[d],P[j]-P[d])>0) ans=max(ans,DFS(d,i,j)+2);
		}
	}
	return ans;
}
void work(void){
	int ans=0;
	for(int i=1;i<=N;i++) ans=max(ans,calc(i));
	printf("%d\n",ans);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d%d",&P[i].x,&P[i].y);
}
int main(){
	freopen("fence1.in","r",stdin);
	freopen("fence1.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}