学步园

/*
题意：从最低的点开始，不能向右拐，问能经过多少点？
能定是经过所有点了   

从最低点开始，求与其极角最小的点，作为新的起点，在需找与这个点成极角最小的点，依次即可
*/
#include<stdio.h>
#include<stdlib.h>
struct point 
{
	int x,y,n;
}dian[60];
int n;
int dis(point a,point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
int cross(point p,point s,point e)
{
	return (e.x-s.x)*(p.y-s.y)-(p.x-s.x)*(e.y-s.y);
}
int cmp(const void *a,const void *b,int zhu)
{
	int ret;
	point *c=(point*)a,*d=(point*)b;
	ret=cross(*d,dian[zhu],*c);
	if(ret!=0) return -ret;
	else if(dis(*c,dian[zhu])>dis(*d,dian[zhu]))
		return 1;
	else return 0;
}
int pro(int  i)
{
	int bao=i;
	int a=i;
	for(i=i+1;i<=n;++i)
	{
		if(cmp(&dian[a],&dian[i],bao-1)>0)
			a=i;
	}
	return a;
}
int main()
{
	int t,i,l,a;
	scanf("%d",&t);
	while(t--)
	{
		l=-1;
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a,&dian[i].x,&dian[i].y);
			dian[i].n=i;
			if(l==-1||(dian[i].y<dian[l].y)||((dian[l].x>dian[i].x)&&(dian[l].y==dian[i].y)))
				l=i;
		}
		dian[n+1]=dian[l];
		dian[l]=dian[1];
		dian[1]=dian[n+1];
		dian[0].x=0,dian[0].y=dian[1].y;
		for(i=2;i<n;i++)
		{
			a=pro(i);
			dian[n+1]=dian[i];
			dian[i]=dian[a];
			dian[a]=dian[n+1];
		}
		printf("%d",n);
		for(i=1;i<=n;++i)
			printf(" %d",dian[i].n);
		printf("\n");
	}
	return 0;
}