UVa 10034

From Algorithmist
Jump to: navigation, 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 o(n^{2}) edges, this can be done in 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 O(n\log n) by a more complex algorithm. The Delaunay Triangulation of a set of points in the plane can be calculated in O(n\log n), with 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 O(n\log n) 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

Solutions[edit]