题解

思路推导

如果直接按任意顺序访问，相邻地点的曼哈顿距离可能接近坐标范围的两倍，点数较大时总路程会超出限制。只按一个坐标排序虽然能限制该坐标方向的总变化，另一个方向仍可能在相邻地点间反复跳动。

把平面划分为若干竖直条带，并在相邻条带中交替按纵坐标从小到大、从大到小访问，可以同时控制两类代价：条带越窄，条带内的横向移动越少；条带越宽，条带数量越少，纵向往返也越少。令两项代价大致相等即可得到合适的条带宽度。

做法

记坐标上界为 $W=2\times10^7$，取

按以下关键字对地点编号排序：

1. 先按条带编号 $\lfloor X_i/B\rfloor$ 从小到大；
2. 偶数编号条带内按 $Y_i$ 从小到大；
3. 奇数编号条带内按 $Y_i$ 从大到小。

排序结果形成一个闭环。找到地点 $1$ 所在位置，对整个循环顺序做一次循环移位，使地点 $1$ 成为第一个输出的地点。

正确性证明

排序结果包含每个地点恰好一次，循环移位不会改变这一性质，也不会改变闭环的边集合，因此输出是以地点 $1$ 开头的排列。

设非空条带数为 $K$。同一条带内相邻地点的横坐标差小于 $B$，这部分横向路程小于 $NB$。条带按横坐标递增访问，条带之间的前进和最后回到起点合计至多 $2W$。

每个条带内纵坐标单调，相邻条带方向相反。把每个条带的纵向单调段及与下一条带的连接一起计算，全部纵向变化至多 $KW$；最后闭环再至多增加 $W$。由于 $K\le\lfloor W/B\rfloor+1$，纵向路程至多 $W^2/B+2W$。

所以闭环总路程不超过

在 $1\le N\le60000$ 的范围内，按上述整数规则取 $B$ 时，该上界始终小于 $10^{10}$。因此输出路线一定满足路程限制，算法正确。

复杂度分析

排序耗时 $O(N\log N)$，其余操作耗时 $O(N)$；空间复杂度为 $O(N)$。