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.
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.
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]
3 1 1 5 5 6 7
KryptonyteMaruf 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. →