Problem E
Landsreisa
Languages
en
is
Stefán and Eva live in Vestmannaeyjar. Eva wants to see the entire country. They intend to visit every location in the country exactly once and then end up back in Vestmannaeyjar. Stefán hates traveling and thus wants to spend the least amount of time traveling between locations. If Stefán travels for too long he gets annoyed which in turn annoys Eva. Eva wants to keep Stefán in a good mood and thus has asked for your help making a travel plan. The shorter the travel plan the more satisfied Stefán will be.
The starting location of Stefán and Eva is location $0$. They always travel with the same speed between locations. It’s possible to travel between any two locations in both directions. To simplify things the world is two dimensional, where each longitude has been converted into an $x$ value and each latitude has been converted into a $y$ value. Since the world is two dimensional we use Euclidean distance.
Input
The input to this problem is not secret like in other problems, it can be found here.
The first line contains an integer $n$, the number of locations. Next there are $n$ lines. Each contains two real numbers $x$ and $y$ where $-25 \leq x \leq -13$ and $63 \leq y \leq 67$. The $i$-th line denotes the coordinates of location $i$. The values have at most $4$ digits after the decimal point. Below there is an image of the given input.
Output
Print the travel plan on one line with $n$ numbers, separated by spaces, where each number is between $0$ and $n - 1$ with each value appearing exactly once. The numbers should signify in what order the locations are visited. The first value should always be $0$.
Scoring
The score is given as an integer $0 \leq x \leq 100$. If the length of your travel plan is $k$ then $x = \left\lfloor 100 \cdot \left( 1 - \frac{k - 63}{100} \right)^4 \right\rfloor $.
