这道题灵活的考察了凸包的性质，是Graham算法的变形，要求的是永不右转的最长路径，其实题目中最大的数量一定是n，这很容易想到，相当于一圈圈的剥洋葱一样，每次取最外面的点，总能取遍所有的点。
我的算法也是这样设计的，每一次都是找凸包，找完当前的凸包以后，以最后一个点为始点，重新按极角排序后再找，直到所有的点都被找遍为止。
这题比较麻烦，模板改动也比较多，要理解几个函数的含义才能做得出来，下面是我的实现代码：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Point{int x,y,k;};
Point pt[61], stk[61];
int Xmult(Point p1,Point p2,Point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
Point p1,p2;
int graham_cp(const void* a,const void* b){
int ret=Xmult(*((Point*)a),*((Point*)b),p1);
return (ret==0)?(Xmult(*((Point*)a),*((Point*)b),p2)>0?-1:1):(ret>0?-1:1);
}
void ASort( int n, Point* pt ){
int i,k=0;
for (p1=p2=pt[0],i=1;i<n;p2.x+=pt[i].x,p2.y+=pt[i].y,i++)
if (p1.y-pt[i].y>eps||((p1.y-pt[i].y==0)&&p1.x>pt[i].x))
p1=pt[k=i];
p2.x/=n,p2.y/=n;
pt[k]=pt[0],pt[0]=p1;
qsort(pt+1,n-1,sizeof(Point),graham_cp);
}
int main(){
int t, n, m, i, j, cnt;
scanf("%d",&t);
while( t-- ){
scanf("%d",&n);
for( i= 0; i< n; i++ ) scanf("%d%d%d",&pt[i].k,&pt[i].x,&pt[i].y);
cnt= 0, m= n;
ASort(m,pt);
while( cnt< n ){
for( stk[cnt++]=pt[0],stk[cnt++]=pt[1],stk[cnt++]=pt[2],i=3,j=1; i< m; i++ ){
for( ;cnt>2&&Xmult(stk[cnt-2],pt[i],stk[cnt-1])>=0; pt[j++]=stk[--cnt] );
stk[cnt++]=pt[i];
}
pt[0]= stk[--cnt], m= j;
qsort(pt+1,m-1,sizeof(Point),graham_cp);
}
printf("%d",n);
for( i= 0; i< n; i++ )
printf(" %d",stk[i].k);
putchar('\n');
}
return 0;
}posted on 2009-06-29 20:49
古月残辉 阅读(781)
评论(0) 编辑 收藏 引用 所属分类:
计算几何