配点 : 100 点
問題文
在二维平面上 有 N 点 p_1,p_2,\dots,p_N 。
p_i 是 您也可以写 (X_i,Y_i) 。多个点不能位于同一坐标。
满足以下条件的点序列 排序 p=(p_1,p_2,\dots,p_N) 要么构建一个 q=(q_1,q_2,\dots,q_N) ,要么宣布它不可能。 对于
- 1\leq i\leq N-2 ,点序列 q_i,q_{i+1},q_{i+2} 按此顺序呈直线或逆时针方向。
- 更准确地说,q_i 的坐标为 (x_i,y_i) ,(x_{i+1} - x_i)(y_{i+2} - y_{i+1}) - (y_{i+1} - y_i)(x_{i+2} - x_{i+1}) \ge 0 成立。
以上问题 请解决 T 测试用例。
制約
- 1\leq T\leq 100
- 3\leq N\leq 3000
- 0\leq X_i,Y_i\leq 10^9
- (X_i,Y_i)\ne (X_j,Y_j) (i\ne j)
- N 的总和为 3000 以下
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出。 打印
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
T 行。
i 行中,i 个测试用例,目的已满足。 如果 q 不存在 -1 。
如果存在,q=(p_{r_1},p_{r_2},\dots,p_{r_N}) 什么时候 r_1,r_2,\dots,r_N ,用空格分隔。 当
如果有多个答案,则输出哪一个并不重要。
入力例 1
1 9 2 4 2 3 2 2 1 1 4 4 4 3 5 2 5 1 6 5
出力例 1
6 9 2 3 5 1 8 7 4
