GitHub 源文件 Markdown English

游耕者（昼）

• 参考时间限制：1.0 秒（参考环境：评测环境与性能；仅供预估）
• 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
• 内存限制：256 MB

背景故事

游耕者还没有自己的农田，每天从住处附近的农场出发，依次到各处农场帮忙耕作，最后返回出发点。白天可以在农场之间沿直线行走，每一段路的消耗按长度向上取整。农场分布在广阔的地图上，需要规划一条消耗较小的巡回路线。

形式化问题描述

平面上有 \(n\) 个农场，编号为 \(1\) 到 \(n\) ，农场 \(i\) 的坐标为 \((x_i,y_i)\) .不同编号的农场可以位于同一坐标。

从农场 \(i\) 到农场 \(j\) 的代价为：

\[ d(i,j)=\left\lceil\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\right\rceil \]

在农场之间选择若干条双向连线，使所有农场连通。连线的端点必须是给定的农场，每条连线的代价按上述距离规则计算；连线交叉处不会新增连接点。设所选连线总代价的最小可能值为 \(M\) .当 \(n=1\) 时，约定 \(M=0\) .

请构造一条从 \(1\) 号农场出发、访问其他每个农场恰好一次并返回起点的路线。设路线总代价为 \(C\) ，满足以下条件即为可接受的答案：

\[ C\le 2.001M+0.001 \]

访问次序以输出的农场编号为准，途经其他农场的坐标不会额外计为一次访问。无需输出 \(C\) 或 \(M\) ，也无需求出最短巡回路线。

输入格式

第一行一个整数 \(n\) .

接下来 \(n\) 行，第 \(i\) 行两个整数 \(x_i,y_i\) ，表示农场 \(i\) 的坐标。

输出格式

输出一行 \(n+1\) 个整数 \(p_0,p_1,\ldots,p_n\) .

• 必须满足 \(p_0=p_n=1\) .
• \(p_0,p_1,\ldots,p_{n-1}\) 必须是 \(1,2,\ldots,n\) 的一个排列。
• \(C=\sum_{i=0}^{n-1}d(p_i,p_{i+1})\) 必须满足上述上界。
• 当 \(n=1\) 时，输出 1 1 .

本题采用特殊评测。输出任意满足要求的路线均可，不必与样例输出相同。

样例 1

输入

3
5 3
1 7
7 7

输出

1 3 2 1

解释

最小连接成本为 \(M=11\) ，示例路线的总代价为 \(C=17\) ，满足 \(C\le2.001M+0.001\) .

样例 2

输入

5
7 3
1 0
-5 3
7 9
9 10

输出

1 4 5 2 3 1

解释

最小连接成本为 \(M=23\) ，示例路线的总代价为 \(C=41\) ，满足 \(C\le2.001M+0.001\) .

样例 3

输入

10
15 616
15 7
1 6794
13 245
1233 44
15 6
97 94
123 321
3020 100
456 987

输出

1 8 4 7 2 6 5 9 10 3 1

解释

最小连接成本为 \(M=10071\) ，示例路线的总代价为 \(C=18468\) ，满足 \(C\le2.001M+0.001\) .

样例 4

输入

1
0 0

输出

1 1

解释

只有一个农场，路线从该农场出发并直接结束，\(M=C=0\) .

样例 5

输入

4
0 0
0 0
3 4
3 4

输出

1 2 3 4 1

解释

农场 \(1,2\) 重合，农场 \(3,4\) 重合，但各编号仍须访问。两处坐标之间的代价为 \(5\) ，因此 \(M=5\) ，示例路线的总代价为 \(C=10\) .

数据范围与保证

• \(1\le n\le400000\) .
• \(-10000\le x_i,y_i\le10000\) ，所有坐标均为整数。
• 允许坐标重合、所有点共线或多个点共圆。

数据分组

分值比例	额外条件
100%	无额外条件