UW Madison ICPC 2019-2020 training 1

Start

2019-09-06 15:00 UTC

UW Madison ICPC 2019-2020 training 1

End

2019-09-13 15:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -42 days 9:24:58

Time elapsed

168:00:00

Time remaining

0:00:00

Problem B
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 $1 \le n \le 10$. After that, $n$ cases follow. Each case starts with a line containing the integer number of islands $1 \le m \le 750$, 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 $[-1\, 000$ to $1\, 000]$ 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 $10^{-3}$ 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