As everyone else, you're a massive Lord of the Rings fan. One of your favourite pastimes is to take a printout of the map of MiddleEarth and mark all the major places. Then you connect them in some kind of pattern. You have a slightly skewed definition of fun.
Anyway, today's pattern is to minimize the amount of ink you need to connect all the places. You connect places by drawing a straight line between them, and you allow yourself to do so between arbitrary pairs of places. In the end, you want to have drawn lines such that there is a connection between any pair of places.
The input begins with a single positive integer on a line by itself indicating the number of test cases, followed by a blank line.
The first line of each test case contains \(0 < n \leq 100\), giving the number of places you have marked on your map. For each freckle, a line follows that contains two real numbers indicating the x and y coordinate of the freckle.
There is a blank line between each two consecutive test cases.
For each test case, your program must print a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles. The output of each two consecutive cases must be separated by a blank line.
1
3
1.0 1.0
2.0 2.0
2.0 4.0
3.41
This is challenge 10034 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.
Please log in to submit your solution.
Difficulty 

Average test runtime  3.83 
Points (changes over time)  10 
Tried by  7 users 
Solved by  6 users 