Vista 8
Time limit0.1sMemory limit128 MB
Given up to a million distinct points in the plane, output a cyclic tour that visits every point and returns to the start, under the Euclidean metric.
- Level
Hard9 of 10
- Topics
- Geometry, Greedy, Sorting, Implementation
- Solved
- No attempts yet
Problem
One day a large unnamed company in Prague decided to install a new operating system (made by another unnamed large company in the USA) on all of its computers. Everybody was excited, because the company that made the OS was very famous and there were many advertisements for the OS, so it had to be the best OS ever. Only the main network administrator did not share their enthusiasm. His doubts were soon confirmed. While installing the new OS on the last computer, all of the other computers froze and could no longer be controlled remotely. The poor administrator now has no other option than to walk physically to each of the computers and restart them manually.
Help the administrator and recommend an order in which he should visit the computers and return to the computer he started with (hopefully without starting another round of reboots there). You know the position of each computer, given by two coordinates (x) and (y). All computers are in the plane, and the distance between any pair of them is given by the Euclidean metric; that is, the distance between computers with coordinates ((x_1), (y_1)) and ((x_2), (y_2)) equals (\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}).
Input
The first line of the input contains one integer (N) (1 ≤ (N) ≤ 1 000 000), the number of computers. Then (N) lines follow, and the (i)-th line contains two integers (x_i), (y_i) (0 ≤ (x_i), (y_i) ≤ 1 000 000), the coordinates of the (i)-th computer. The computers are placed at distinct locations.
Output
The output must contain (N) + 1 lines with the numbers of the computers in the order of the recommended journey. The last computer must be the same as the first one. The circuit can start at any computer.