Description

一位旅行商收到了一份需要在一次旅途中访问的城市列表。他可以从任意一个城市开始和结束旅程，只要每个城市至少访问一次即可。他不需要从同一个城市开始和结束。

这位旅行商注意到他的同行们在规划和寻找最优路线时花费了太多时间。因此，他决定采用一种不同且更系统的方法来规划自己的路线。

他首先会将所有城市分为左半部分和右半部分。如果城市数量为奇数，则右半部分比左半部分多一个城市。然后，他会选择其中一半，先访问该半部分的所有城市，再访问另一半的所有城市。

为了访问选定的左/右半部分，他会将这部分城市再分为下半部分和上半部分。如果这部分城市数量为奇数，则上半部分比下半部分多一个城市。同样地，他会先访问其中一半的所有城市，再访问另一半的所有城市。

他会不断交替地按照横向和纵向将城市分半，直到得到完整的旅行路径。请计算旅行商用这种方式能够获得的最短路径长度。

Input Format

第一行包含旅行商要访问的城市数量 $N$。接下来的 $N$ 行，每行包含两个用空格分隔的整数坐标 $X_i$ 和 $Y_i$，表示该城市在平面上的位置。保证所有城市的 $X_i$ 坐标互不相同，所有 $Y_i$ 坐标也互不相同。

Output Format

第一行输出旅行商路径的最小长度。如果你的答案与官方答案的差距不超过 $10^{-4}$，则视为正确。第二行输出旅行商访问城市的顺序，用空格分隔。城市编号从 $1$ 到 $N$，按输入顺序编号。如果有多种方案，可以输出任意一种。

6
5 1
9 6
2 5
3 3
10 4
7 2

13.142182
3 4 1 6 5 2

Hint

说明

旅行商首先访问左半部分（城市 1、3 和 4），然后访问右半部分（城市 2、5 和 6）。

为了访问城市 1、3 和 4，他首先访问上半部分（城市 3 和 4），再访问下半部分（城市 1）。上半部分中的城市被分为左半部分（城市 3，先访问）和右半部分（城市 4，后访问）。

城市 2、5 和 6 被分为下半部分（城市 6）和上半部分（城市 2 和 5）。这里，旅行商先访问下半部分。然后继续访问上半部分，在上半部分中，先访问右半部分（城市 5），最后访问左半部分（城市 2）。

输入范围

• $1 \leq N \leq 1000$
• $0 \leq X_i, Y_i \leq 10^6$

由 ChatGPT 4.1 翻译