Problem C
Flygildi
Languages
en
is

The webstore Amazon has in the last few years been planning a new way to deliver packages to customers using drones1. When the new delivery system is up and running customers will be able to get their deliveries within just a few hours rather than a few days.
Each drone gets a few packages to deliver at a time, and
each package has a certain destination it needs to be delivered
to. The area the drones fly over is modeled as a two
dimensional coordinate system, where the Amazon warehouse is
located at
It’s clear that the order in which the drone visits the
delivery locations matters, since a bad order could mean that
the drone takes a far longer route to drop off the packages
than is necessary. Amazon has hired you to solve this problem.
Given the number of packages
Input
The first line contains the integer
Output
One line containing the shortest path the drone can take.
The answer is considered correct if its absolute or relative
error from the correct answer is at most
Explanation of Sample Inputs
In the first sample there are only two packages. In this
case it does not matter in what order they are delivered. If
the drone flies in a direct line each time then the length will
be
![\includegraphics[width=0.4\textwidth ]{sample3.png}](/problems/flygildi/file/statement/en/img-0002.png)
The third sample is shown in the image above. Here the
shortest path is to drop the packages off in the order
Scoring
The solution will be tested on differently hard input data and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.
Group |
Points |
Constraints |
1 |
10 |
|
2 |
10 |
|
3 |
20 |
|
4 |
20 |
|
5 |
40 |
|
Sample Input 1 | Sample Output 1 |
---|---|
2 0 1 1 0 |
3.4142135624 |
Sample Input 2 | Sample Output 2 |
---|---|
3 0 1 0 2 0 4 |
8.0000000000 |
Sample Input 3 | Sample Output 3 |
---|---|
4 0 10 2 12 10 0 12 2 |
39.7989898732 |
Footnotes
- Drones are small automated flying robots.