Systematic salesman

A travelling salesman has received a list of cities that he must visit in a single journey. He may start and end his tour in any city as long as he visits each city at least once. He doesn’t have to start and finish in the same city. The travelling salesman noticed that his fellow travelling salesmen are spending way too much time planning and finding an optimal route. Therefore, he has decided to take a different, more systematic approach to planning his route.

He will first split all the cities into the left half and the right half. If the number of cities is odd, the right half will contain one city more than the left. He will then pick one of the halves and visit all the cities in that half before visiting any of the cities in the other half.

To visit the cities in the selected left/right half, he will split this set of cities into the lower and upper half. In case of an odd number of cities in this set, the upper half will contain an extra city. Again, he will first visit all cities in one of these halves before visiting any of the cities in the other half.

He will continue applying the same logic of alternatingly splitting the cities in half horizontally and vertically until he obtains the complete path of the journey. Compute the shortest path that visits all cities that the salesman can obtain in this way.

The first line contains the number of cities $N$ that the salesman wants to visit. Locations of these cities are given in the $N$ lines that follow. The location of each city is defined by a space-separated pair of integer coordinates $X\_i$ and $Y\_i$, which describe its location on a plane. It is guaranteed that $X\_i$ coordinates of all cities are distinct. The same holds for all $Y\_i$ coordinates.

In the first line, print the minimum length of the salesman’s path. The length will be considered correct if it differs from the official solution by at most $10^{-4}$. In the second line output a space-separated list of cities as visited by the salesman. The cities are numbered from $1$ to $N$ in order as given in the input. If there are several solutions, you can output any of them.

• $1 ≤ N ≤ 1000$
• $0 ≤ X\_i , Y\_i ≤ 10^6$

The salesman first visits the left half (cities $1$, $3$ and $4$) and then the right half (cities $2$, $5$ and $6$).

To visit cities $1$, $3$ and $4$, he first visits the upper half (cities $3$ and $4$) before the lower half (city $1$). The cities in the upper half are split into the left half (city $3$), visited first, and the right half (city $4$), visited afterwards.

Cities $2$, $5$ and $6$ are split into the lower half (city $6$) and the upper half (cities $2$ and $5$). Here, the salesman first visits the lower half. He continues his route with the upper half, where he first visits the right half (city $5$) and concludes with the left half (city $2$).