Minimum Spanning Tree for Road Construction

Given \( n \) buildings located at coordinates \((x_i, y_i)\) for \(1 \leq i \leq n\), you are required to construct a network of roads such that all the buildings are connected. The cost to connect any two buildings \( i \) and \( j \) is the Euclidean distance between them, given by:

\( d(i,j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \)

Your task is to compute the minimum total length of roads needed to connect all the buildings. In other words, find the weight of the Minimum Spanning Tree (MST) for the complete graph in which vertices represent buildings and edge weights are the Euclidean distances between buildings. The answer must be accurate within an absolute or relative error of \(10^{-6}\).

inputFormat

The first line contains an integer \( n \) indicating the number of buildings. Each of the next \( n \) lines contains two space-separated integers representing the coordinates \( x_i \) and \( y_i \) of the \( i^{th} \) building.

outputFormat

Output a single line containing the minimum total length of roads needed to connect all the buildings. The output should be a floating-point number with an absolute or relative error of at most \(10^{-6}\).

4
0 0
0 1
1 0
1 1

3.0000000000