UVa 10034

From Algorithmist

Contents 1 10034 - Freckles 2 Summary 3 Explanation 4 Input 5 Output

[edit] 10034 - Freckles

• http://acm.uva.es/p/v100/10034.html

[edit] Summary

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

[edit] Explanation

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

[edit] Input

1

3
1.0 1.0
2.0 2.0
2.0 4.0

[edit] Output

3.41