# UVa 10034

Jump to navigation
Jump to search

## 10034 - Freckles[edit]

## Summary[edit]

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

## Explanation[edit]

Use any minimum spanning tree algorithm, and compute the weight. Since there are edges, this can be done in , 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 by a more complex algorithm. The Delaunay Triangulation of a set of points in the plane can be calculated in , with 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 bound. This is not necessary for this problem.

## Input[edit]

1 3 1.0 1.0 2.0 2.0 2.0 4.0

## Output[edit]

3.41