# UVa 10034

## Summary

Given N (less than 100) points in the plane, find the weight of the minimum spanning tree.

## Explanation

Use any minimum spanning tree algorithm, and compute the weight. Since there are ${\displaystyle o(n^{2})}$ edges, this can be done in ${\displaystyle O(n^{2})}$, which is fast enough for this problem.

Note that the minimum spanning tree of a set of points in the plane can be found in ${\displaystyle O(n\log n)}$ by a more complex algorithm. The Delaunay Triangulation of a set of points in the plane can be calculated in ${\displaystyle O(n\log n)}$, with ${\displaystyle O(n)}$ edges in the resultant graph. Since the minimum spanning tree is a subset of the Delaunay triangulation, we can apply any of the MST algorithms on the resultant Delaunay triangulation and thus achieving the ${\displaystyle O(n\log n)}$ bound. This is not necessary for this problem.

```1

3
1.0 1.0
2.0 2.0
2.0 4.0
```

```3.41
```