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 Middle-Earth 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
Please log in to submit your solution.
|Average test runtime||3.83|
|Points (changes over time)||10|
|Tried by||7 users|
|Solved by||6 users|