分数: 525 点
问题陈述
有 N 位置编号 1 to N 在二维平面上。地点 i 位于坐标处 (X_i, Y_i).
您将从以下位置开始 1,访问每个位置一次,然后返回该位置 1.
移动地点 i 到位置 j 需要 \vert X_i - X_j \vert + \vert Y_i - Y_j \vert 秒。
输出访问所有位置并返回位置的路线 1 内 10^{10} 从位置开始的秒数 1。保证在给定的约束下至少存在一条这样的路由。
约束
- 1 \leq N \leq 6 \times 10^4
- 0 \leq X_i \leq 2 \times 10^7
- 0 \leq Y_i \leq 2 \times 10^7
- (X_i, Y_i) \neq (X_j, Y_j) if i \neq j
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
输出
让 p_i 是 i访问过的第一个位置 (1 \leq i \leq N),并按以下格式输出您的答案。
p_1 p_2 \dots p_N
如果满足以下所有条件,则认为您的答案是正确的。
- (p_1, p_2, \dots, p_N) 是一个排列 (1, 2, \dots, N).
- p_1 = 1
- 出租 d(i, j) 是从位置移动所需的秒数 i 到位置 j, \displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1} ) \leq 10^{10}.
如果有多个有效答案,则接受其中任何一个。
示例输入 1
3 0 6 3 5 2 4
示例输出 1
1 3 2
\displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10,因此输出满足条件。
示例输入 2
10 9706344 19786176 19341349 15565412 5711023 19068083 12521132 14054301 14767612 17088029 14961700 18526945 13801766 5740101 6581153 8643675 13176196 16586661 4086263 5172719
示例输出 2
1 5 2 6 4 7 9 8 3 10