AT_abc448_f [ABC448F] Authentic Traveling Salesman Problem

在一个二维平面上有编号为 $1$ 至 $N$ 的 $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$ 的路径。保证在给定的数据范围下至少存在一条这样的路线。

输入格式如下： > $N$ > > $X_1$ $Y_1$ > $X_2$ $Y_2$ > $\vdots$ > $X_N$ $Y_N$

设 $p_i (1 \leq i \leq N)$ 为访问过的 $i$ 个位置，并按以下格式输出答案。 > $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 \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$； - 如果 $i \neq j$，那么 $(X_i, Y_i) \neq (X_j, Y_j)$； - 所有输入值均为整数。 #### 样例解释 #1 $\displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10$ ，因此输出满足条件。