Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Chemical Reaction

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]

Samples

InputOutput
3
1 1
5 5
6 7
7.892922226992170

Author
  • Kryptonyte's Avatar

    Kryptonyte

    Maruf is a student of Islamic University of Technology. In his journey of sport programming he finds inspiration from the simple things in life and aims to push beyond what he has already mastered.
Discussion
Submit

Login to submit