Limits 2s, 1.0 GB

In this problem you will be dealing with chemical reaction.
In real life, the simulation of a chemical reaction is much more complicated.
We normalize the problem in such a way so that we can get some low level
features from our data.

We consider that, each of the chemical exists in a 2D Cartesian coordinate system instead of 3D.

To make a bond, at the initial time two compounds will create a bridge and other
compounds will connect to the bridge. The cost of creating such a bond is,

Total cost = Cost of creating the bridge + cost of adding each of the compound to the bridge.

Cost of creating the bridge is distance between the position of two points.

Cost of adding each of the compound to the bridge is the shortest distance from the
position of the compound to the bridge.

No compound can create a bond alone. At least two compounds should participate to create
a bond.

In this problem, you will be given positions (2D coordinate) of N points.
You need to calculate the minimum cost as a low level feature of
having a chemical reaction where all the compounds will participate to at least one bond.

No two bonds will interfere each other while doing the simulation of the chemical reaction.

Input

Each case starts with a line containing an integers N (2 ≤ N ≤ 13) denoting number of compounds. Next N line contains positions of each compound. Each of the line contains 2 integer X (-100001 ≤ X ≤ 100001) and Y (-100001 ≤ Y ≤ 100001) where X if cartesian x coordinate and Y is the cartesian y coordinate.

Output

For each test case output the minimum cost in a single line. Errors less than 10-6 will be ignored. [This is a special judge problem]

Sample

InputOutput
3
1 1
5 5
6 7
7.892922226992170

Submit

Login to submit.

Statistics

57% Solution Ratio
Bishal_GEarliest, Jul '16
Kuddus.6068Fastest, 0.1s
Bishal_GLightest, 5.5 MB
AungkurShortest, 6517B
Toph uses cookies. By continuing you agree to our Cookie Policy.