Hide

Problem D
Island Hopping

You are a contractor for the small independent nation of Microisles, which is far out in the Pacific ocean, and made up of a large number of islands. The islanders travel between islands on boats, but the government has hired you to design a set of bridges that would connect all the islands together. However, they want to do this at a minimum cost. Cost is proportional to bridge length, so they want to minimize the total length of all bridges put together. You need to decide which bridges should connect which islands.

Input

The first line contains an integer 1n10. After that, n cases follow. Each case starts with a line containing the integer number of islands 1m750, followed by m lines each containing the real-valued horizontal and vertical position of a bridge endpoint for the corresponding island. All bridge endpoints are, of course, unique. Each coordinate is in the range [1000 to 1000] meters and has at most 3 digits past the decimal point.

Output

For each test case, output the total length of bridges needed to connect all the islands accurate to relative and absolute error of 103 meters.

Sample Input 1 Sample Output 1
2
3
0.0 0.0
0.0 1.0
1.0 0.0
10
30.0 38.0
43.0 72.0
47.0 46.0
49.0 69.0
52.0 42.0
58.0 17.0
73.0 7.0
84.0 81.0
86.0 75.0
93.0 50.0
2.000
168.01015709273446
Hide

Please log in to submit a solution to this problem

Log in