#include<stdio.h>
#include<math.h>
#include<memory.h>
//using namespace std;
#define eps 1e-8
#define MAXN 50
#define PI 3.1415926535898
struct point
{ double x,y;};
point planet[MAXN+1];
bool visit[MAXN+1];
int ans[MAXN+1];
double xmult(point p0,point p1,point p2){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dmult(point p0,point p1,point p2){
return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
double distance(point p1,point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int main()
{
int t,indice,i,j,k,n;
double max;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%lf%lf",&indice,&(planet[i].x),&(planet[i].y));
memset(visit,0,sizeof(visit));
int next=1;
for(i=2;i<=n;i++)
if(planet[next].y>planet[i].y)
next=i;
else if(planet[next].y == planet[i].y)
if(planet[next].x>planet[i].x)
next=i;
point p1,p0;
p1.x=0;
p1.y=planet[next].y;
p0.x=planet[next].x;
p0.y=planet[next].y;
k=0;
double thta,max;
for(j=1;j<=n;j++)
{
visit[next]=true;
ans[k++]=next;
max=2*PI;
for(i=1;i<=n ; i++)
{
if(visit[i]) continue;
double xmul=xmult(p0,p1,planet[i]);
double dmul=dmult(p0,p1,planet[i]);
if( xmul<=0)
{
if(dmul==0 )
thta=3*PI/2.0;
else
if(dmul<0 ) thta=PI+atan(xmul/dmul);
else thta=2*PI+atan(xmul/dmul);
}
if( thta<max ||
(fabs(thta-max)<eps && fabs(distance(p0,planet[i])-distance(p0,planet[next]))<eps)
)
{ next=i;max=thta;}
}
p1.x=p0.x;
p1.y=p0.y;
p0.x=planet[next].x;
p0.y=planet[next].y;
}
printf("%d",k);
for(i=0;i<k;i++)
printf(" %d",ans[i]);
printf("\n");
}
return 0;
}posted on 2009-10-05 12:12
wyiu 閱讀(112)
評論(0) 編輯 收藏 引用 所屬分類:
POJ