首页 > 代码库 > POJ 1696

POJ 1696

2024-07-14 22:53:45   225人阅读

这题是明显的TU包变形。

使用卷包裹法可解，而且是必定可以经过所有点的。直观可知，当经过某点后，相当于把之前的点抹去，求剩下点的TU包，递归下去，也就能把点全部经过了。

于是，只需把经过的点标记一下就可以了。

#include <iostream>#include <cstdio>#include <algorithm>#include <queue>#include <cmath>using namespace std;const double inf=10000000;const double eps=0.00000001;struct point {	double x,y;	int num;}p[60];bool vis[60];queue<int>que;struct vect{	double x,y;};double dist(point a,point b){	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double cross(point a,point b,point c,point d){	return (a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x);}int n;int main(){	int t;	scanf("%d",&t); double a,b;	while(t--){		scanf("%d",&n);		point start; start.x=inf; start.y=inf; int dep;		for(int i=0;i<n;i++){			scanf("%d%lf%lf",&p[i].num,&p[i].x,&p[i].y);			if(p[i].y<start.y){				start.x=p[i].x; start.y=p[i].y; start.num=p[i].num;				dep=i;			}			else if(p[i].y==start.y){				if(p[i].x<start.x){					start.x=p[i].x; start.num=p[i].num;					dep=i;				}			}		}	//	cout<<start.x<<‘ ‘<<start.y<<endl;		point last; last.x=0; last.y=start.y;		que.push(start.num);		memset(vis,false,sizeof(vis));		vis[dep]=true; point tmp;		while(true){			bool flag=false;			for(int i=0;i<n;i++){				if(vis[i]==false){					if(cross(start,last,p[i],start)>=0){						tmp=p[i];						dep=i;						flag=true;						break;					}				}			}		//	cout<<dep<<"YES"<<endl;			if(!flag) break;			for(int i=0;i<n;i++){				if(vis[i]==false){					if(cross(start,last,p[i],start)<0) continue;					double res=cross(tmp,start,p[i],start);					if(res<0){						tmp=p[i];						dep=i;					}					else if(res==0){						if(dist(p[i],start)+eps<dist(tmp,start)){							tmp=p[i];							dep=i;						}					}				}			}			que.push(tmp.num);			//cout<<dep<<endl;			vis[dep]=true;			last=start;			start=tmp;		}		printf("%d",n);		for(int i=0;i<n;i++){			printf(" %d",que.front());			que.pop();		}		printf("\n");	}	return 0;}

　　


联系
我们