首页 > 代码库 > POJ 1696
POJ 1696
这题是明显的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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。