Vista 9
Time limit0.1sMemory limit128 MB
Given up to a million points in the plane, output a cyclic tour that visits each point once and returns to the start.
- 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 the other computers froze and could no longer be controlled remotely. The poor administrator now has no other option than to walk to each computer and restart it by hand.
Help the poor administrator and recommend an order in which he should visit the computers and return to the computer he started from (hopefully without starting another round of reboots there). You are given the position of each computer as two coordinates (x) and (y). All computers lie in the plane, and the distance between any pair of them is given by the Euclidean metric, that is, the distance between the computers with coordinates ((x_1), (y_1)) and ((x_2), (y_2)) is (\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 whole numbers (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 should contain (N) + 1 lines containing 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.