//Stephen Siena //CSE 40872 - Problem 22 //November 13, 2009 #include #include #include #include using namespace std; double mst(vector, vector, int); int main(){ while(1){ int nPoints; cin >> nPoints; if (nPoints == 0) break; vector xCoords; vector yCoords; for(int i = 0; i < nPoints; i++){ float x, y; cin >> x; cin >> y; xCoords.push_back(x); yCoords.push_back(y); } double distance = mst(xCoords, yCoords, nPoints); cout << fixed; cout << setprecision(2); cout << distance << endl; } return 0; } double mst(vector xCoords, vector yCoords, int n){ double totalDistance = 0; vector connected; bool completeTree = false; if (xCoords.size() < 2) return 0; connected.resize(n); connected[0] = true; for (int i = 1; i < n; i++){ connected[i] = false; } while (!completeTree){ double smallestDistance = -1; double tempDistance; int newPoint; for (int i = 0; i < n; i++){ if (connected[i]){ for (int j = 0; j < n; j++){ if (!connected[j]){ tempDistance = sqrt(pow(xCoords[i]-xCoords[j],2)+pow(yCoords[i]-yCoords[j],2)); if ((tempDistance < smallestDistance) || smallestDistance == -1){ smallestDistance = tempDistance; newPoint = j; } } } } } totalDistance += smallestDistance; connected[newPoint] = true; completeTree = true; for (int i = 0; i < n; i++){ if (!connected[i]){ completeTree = false; break; } } } return totalDistance; }