就是求点逆时针旋转的次序。
第一次选取最左下角的点。然后每次选取一个极角最小的点。
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<stack>
using namespace std;
#define maxn 200000
#define eps 0.00001
#define zero(x) ((fabs(x)<eps)?0:x)
#define INF 999999
#define LL long long
#define mod 1000003
struct point
{int x;int y;int index;
} p[55],pp,ds;
int chaji(point a,point b,point c,point d)
{return (b.x-a.x)*(d.y-c.y)-(d.x-c.x)*(b.y-a.y);
}
int dis(point a,point b)
{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int cmp(point a,point b)
{int d=chaji(ds,a,ds,b);if(d!=0)return d>0;return dis(ds,a)<dis(ds,b);
}
int pan(point a,point b,point c)
{if(chaji(a,b,b,c)>=0)return 1;return 0;
}
int main()
{int T,i,ip,n;scanf("%d",&T);while(T--){pp.x=INF;pp.y=INF;scanf("%d",&n);for(i=0; i<n; i++){cin>>p[i].index>>p[i].x>>p[i].y;if(pp.y>p[i].y||(pp.y==p[i].y&&pp.x>p[i].x)){ip=i;pp.x=p[i].x;pp.y=p[i].y;}}cout<<n;cout<<" "<<p[ip].index;swap(p[0],p[ip]);ds=p[0];for(i=1;i<n;i++){sort(p+i,p+n,cmp);ds=p[i];cout<<" "<<ds.index;}cout<<endl;}return 0;
}
