Traveling Salesman 3

Interview

Time limit1sMemory limit512 MB

Summary

Find the minimum-length round trip that visits all N cities exactly once and returns to the start, where N is at most 16.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Brute force, Geometry
Solved: No attempts yet

Problem

The traveling salesman problem, known in English as the Traveling Salesman problem (TSP), is treated as one of the most important problems in computer science. There are many variants, but here we look at the most general form.

There are cities numbered 1 through N, and there is a road between every pair of cities. A salesman wants to plan a tour that starts at some city, visits all N cities, and returns to the starting city. He cannot visit a city he has already visited, except for returning to the starting city at the very end. Many such tours may exist, and he wants to choose the one with the lowest cost.

The cost of going from city A to city B equals the distance between the two cities. If city A has coordinates $(x_A, y_A)$ and city B has coordinates $(x_B, y_B)$ , the distance between them is $\sqrt{(x_B-x_A)^2 + (y_B-y_A)^2}$ .

Given the number of cities N and the positions of all cities, write a program that finds the traveling salesman's tour with the lowest cost.

Input

The first line gives the number of cities N. (2 ≤ N ≤ 16) The next N lines give the coordinates x, y of each city. Every coordinate is an integer greater than or equal to -1,000 and less than or equal to 1,000. No two cities share the same position.

Output

Print the minimum cost of the traveling salesman's tour on the first line. Absolute or relative error up to $10^{-6}$ is allowed.

Examples3

Example 1
Input
```
4
1 1
2 2
1 2
2 1
```
Expected output
```
4.0
```
Example 2
Input
```
4
1 1
5 3
3 1
3 3
```
Expected output
```
9.656854249
```

Example 3

Input

Expected output

3091.3804200514593