【UER #9】赶路

——-一定有解。。

$x_1\leq x_i\leq x_n$

将中间的点按照$(x_i,y_i)$排序，然后依次连过去即可

$x_1=y_1=0$，四个象限均存在点

将所有点极角排序，然后走一圈即可

$O(n\log n)$

不妨设$x_1<x_n$

将$1,n$以外所有点分成三部分，即左边| 1 | 中间 | n | 右边

左边右边考虑极角排序转圈走，中间按照$(x_i,y_i)$走

发现两边极角排序之后转圈走不一定能够走到中间去，可能会与转圈时的路径相交

但是实际上画图就会发现，如果顺时针走的路径会相交，逆时针走一定不相交

因此对于左右枚举顺时针还是逆时针即可，4中情况，每种$O(n)$检查线段相交

总能构造一组合法解

预处理需要排序，因此复杂度为$O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#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();
	}
}