#include #include #include #include using namespace std; double dist(pair one, pair two) { return sqrt((double)(one.first - two.first)*(double)(one.first-two.first) + (double)(one.second - two.second)*(double)(one.second - two.second)); } struct Edge { int loy; int hiy; double weight; }; struct EdgeComp { bool operator() (const Edge& one, const Edge& two) { if (one.weight < two.weight) { return true; } else if (one.weight > two.weight) { return false; } else { if (one.loy <= two.loy) { return true; } else { return false; } } } }; void addEqualNeighbours( set& eN, vector >& equalNeighbours, int index) { eN.insert(index); for (int i = 0; i < equalNeighbours[index].size(); i++) { if (eN.find(equalNeighbours[index][i]) == eN.end()) { eN.insert(equalNeighbours[index][i]); addEqualNeighbours(eN, equalNeighbours, equalNeighbours[index][i]); } } } void clearEqualNeighbours( vector& foundParent, vector >& equalNeighbours, int index) { set eN; addEqualNeighbours(eN, equalNeighbours, index); set::const_iterator itr_end = eN.end(); for (set::const_iterator itr = eN.begin(); itr != itr_end; itr++) { foundParent[*itr] = true; } } int main() { int N; while (cin >> N) { if (N <= 0) break; int M = 1; // Number of met centers allowed; int cM = 0; // Cost of each met center vector > cities; set sorted; for (int i = 0; i < N; ++i) { pair c; cin >> c.first >> c.second; cities.push_back(c); for (int j = 0; j < i; j++) { Edge e; e.weight = dist(cities[j], c); if (cities[j].second <= c.second) { e.loy = j; e.hiy = i; } else { e.loy = i; e.hiy = j; } sorted.insert(e); } } vector > equalNeighbours(N); vector foundParent(N, false); double totalLength = 0.0; int selected = 0; set::const_iterator itr_end = sorted.end(); for (set::const_iterator itr = sorted.begin(); itr != itr_end; itr++) { if (selected == N - M) { break; } const Edge& e = *itr; if (cities[e.loy].second == cities[e.hiy].second) { if (!foundParent[e.loy] || !foundParent[e.hiy]) { selected++; totalLength += e.weight; if (!foundParent[e.loy] && !foundParent[e.hiy]) { set eN; eN.insert(e.loy); addEqualNeighbours(eN, equalNeighbours, e.loy); if (eN.find(e.hiy) == eN.end()) { equalNeighbours[e.loy].push_back(e.hiy); equalNeighbours[e.hiy].push_back(e.loy); } else { selected--; totalLength -= e.weight; } } else if (!foundParent[e.loy]) { foundParent[e.loy] = true; clearEqualNeighbours(foundParent, equalNeighbours, e.loy); } else { foundParent[e.hiy] = true; clearEqualNeighbours(foundParent, equalNeighbours, e.hiy); } } } else { if (!foundParent[e.hiy]) { selected++; totalLength += e.weight; foundParent[e.hiy] = true; clearEqualNeighbours(foundParent, equalNeighbours, e.hiy); } } } printf("%.2f\n",(M*cM + totalLength)); } return 0; }