【UER #9】赶路
-----一定有解。。
(x_1leq x_ileq x_n)
将中间的点按照((x_i,y_i))排序，然后依次连过去即可
[
]
(x_1=y_1=0)，四个象限均存在点
将所有点极角排序，然后走一圈即可
[
]
(O(nlog n))
不妨设(x_1<x_n)
将(1,n)以外所有点分成三部分，即左边| 1 | 中间 | n | 右边
左边右边考虑极角排序转圈走，中间按照((x_i,y_i))走
发现两边极角排序之后转圈走不一定能够走到中间去，可能会与转圈时的路径相交
但是实际上画图就会发现，如果顺时针走的路径会相交，逆时针走一定不相交
因此对于左右枚举顺时针还是逆时针即可，4中情况，每种(O(n))检查线段相交
总能构造一组合法解
预处理需要排序，因此复杂度为(O(nlog n))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
template <class T=int> T rd(){
T s=0; int f=0;
while(!isdigit(IO=getchar())) f|=IO=='-';
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=510,INF=1e9+10;
const db eps=1e-7;
int n,m;
struct Node{
db x,y;
Node(){}
Node(db x,db y):x(x),y(y){ }
bool operator < (const Node __) const { return x!=__.x?x<__.x:y<__.y; }
Node operator - (const Node &t) const { return Node(x-t.x,y-t.y); }
db operator * (const Node &t) const { return x*t.x+y*t.y; }
db operator ^ (const Node &t) const { return x*t.y-y*t.x; }
void turn(db t){
db a=x*cos(t)-y*sin(t),b=x*sin(t)+y*cos(t);
x=a,y=b;
}
db tan() const { return atan2(x,y); }
} A[N];
int Cross(int x,int y,int a,int b){
if(((A[x]-A[y])^(A[a]-A[b]))==0) return 0;
db l=(A[a]-A[x])^(A[y]-A[x]),r=(A[b]-A[x])^(A[y]-A[x]);
if((l<0)^(r>0)) return 0;
swap(a,x),swap(b,y);
l=(A[a]-A[x])^(A[y]-A[x]),r=(A[b]-A[x])^(A[y]-A[x]);
if((l<0)^(r>0)) return 0;
return 1;
}
int L[N],LC,R[N],RC,T[N],TC;
int P[N];
int Work(){
int C=0;
P[++C]=1;
rep(i,1,LC) P[++C]=L[i];
rep(i,1,TC) P[++C]=T[i];
rep(i,1,RC) P[++C]=R[i];
P[++C]=n;
if(LC) rep(i,2,LC) if(Cross(P[LC+1],P[LC+2],P[i],P[i-1])) return 0;
if(RC) drep(i,n,n-RC+2) if(Cross(P[n-RC],P[n-RC-1],P[i],P[i-1])) return 0;
return 1;
}
void Solve(){
rep(i,0,1) {
rep(j,0,1) {
if(Work()) {
rep(i,1,n) printf("%d ",P[i]);
puts("");
return;
}
reverse(R+1,R+RC+1);
}
reverse(L+1,L+LC+1);
}
}
int main(){
rep(kase,1,rd()){
rep(i,1,n=rd()) A[i].x=rd(),A[i].y=rd();
db t=1.0*(rand()+2)/(rand()+2);
rep(i,1,n) A[i].turn(t);
if(A[1].x>A[n].x) rep(i,1,n) A[i].x=-A[i].x;
LC=RC=TC=0;
rep(i,2,n-1) if(A[i].x<A[1].x-eps) L[++LC]=i;
else if(A[i].x-eps>A[n].x) R[++RC]=i;
else T[++TC]=i;
sort(T+1,T+TC+1,[&](int x,int y){ return A[x].x<A[y].x; });
sort(L+1,L+LC+1,[&](int x,int y){ return (A[x]-A[1]).tan()<(A[y]-A[1]).tan(); });
sort(R+1,R+RC+1,[&](int x,int y){ return (A[x]-A[n]).tan()<(A[y]-A[n]).tan(); });
Solve();
}
}