PKU 2560 Freckles

typedef double Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

pair<Weight, Edges> minimumSpanningForest(const Graph &g) {
  int n = g.size();
  UnionFind uf(n);
  priority_queue<Edge> Q;
  REP(u, n) {
	  for (Edges::const_iterator e = g[u].begin(), eEnd = g[u].end(); e != eEnd; ++e) {
		  if (u < e->dst) Q.push(*e);
	  }
  }

  Weight total = 0;
  Edges F;
  while (F.size() < n-1 && !Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (uf.unionSet(e.src, e.dst)) {
      F.push_back(e);
      total += e.weight;
    }
  }
  return pair<Weight, Edges>(total, F);
}

typedef complex<double> P;

int main() {
	int N;
	cin >> N;
	vector<P> ps;
	for (int n = 0; n < N; ++n) {
		double x, y;
		cin >> x >> y;
		ps.push_back(P(x, y));
	}

	Graph g(N);
	for (int from = 0; from < N; ++from) {
		for (int to = 0; to < N; ++to) {
			if (from == to) {
				continue;
			}

			const double d = abs(ps[from] - ps[to]);
			g[from].push_back(Edge(from, to, d));
		}
	}

	const double answer = minimumSpanningForest(g).first;
	printf("%.02f\n", answer);
}