就是求点逆时针旋转的次序。
第一次选取最左下角的点。然后每次选取一个极角最小的点。
#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;
}