10034 - Freckles
Given N (less than 100) points in the plane, find the weight of the minimum spanning tree.
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.
1 3 1.0 1.0 2.0 2.0 2.0 4.0