Minimum Spanning Tree of Points

This problem involves computing the total length of the Minimum Spanning Tree (MST) of a set of points in the 2D plane using Prim's algorithm. Given a set of points, the weight of an edge between any two points is the Euclidean distance between them. The Euclidean distance between two points \( (x_1, y_1) \) and \( (x_2, y_2) \) is given by \( \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \).

You are given several test cases. Each test case starts with an integer \( N \) indicating the number of points, followed by \( N \) lines each containing two integers representing the coordinates \( x \) and \( y \) of the points. The input terminates with a test case where \( N = 0 \). For each test case, calculate the total length of the MST and output the result with 6 decimal places.

inputFormat

The input consists of multiple test cases. Each test case begins with an integer \( N \) (\( 1 \leq N \leq 10^3 \)) representing the number of points. The next \( N \) lines contain two space-separated integers each denoting the \( x \) and \( y \) coordinates of a point. A test case with \( N = 0 \) signifies the end of input and should not be processed.

outputFormat

For each test case, output a single line containing the total length of the MST with exactly 6 decimal places.

4
0 0
0 1
1 0
1 1
3
0 0
2 2
3 3
0

3.000000
4.242641