[USACO Dec08]巨大的围栏Largest Fence解题报告

题目


分析

这是道挺有意思的计算几何题……

算法就是:枚举凸包的最左下点B,然后将所有合法的点按相对于B的极角序排序,这样凸包上的点一定是顺序选的。然后记忆化搜索:设状态f(B,p2,p3)代表:最左下点为B,凸包上选的最后一个点为p2,正在测试选不选p3.那么有两种转移:①不选p3,将p3改为p2->p3这条射线沿逆时针旋转卡到的第一个点。②选p3,将p2改为p3,p3改为以p3为起点,方向为p2->p3的射线沿逆时针旋转卡到的第一个点。


这个过程很像是Graham和卷包裹法的某种综合。


“卡到的第一个点”暴力计算是O(N^3)的,那么如果在每次枚举B时都计算一次会是O(N^4)的。不过实际上我们只需要开始计算一下,记忆化搜索中跳过那些不合法的点即可。


ps:我怎么也开始写意识流题解了……身败名裂……

pps:我擦,意识流题解真省事……


代码

#include
#include
#include
#include
#include
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<<"("<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;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注