← 返回题目列表

AtCoder · pakencamp_2025_day3_c

C. 不要顺时针

中文机器翻译题面 查看原题

配点 : 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