/** * Sample solution for Underground Cables * Steven J Zeil, 10/25/2010 */ #include #include #include #include #include using namespace std; int x[1000]; int y[1000]; bool connected[1000]; double distanceFromConnectedNodes[1000]; double dist (int i, int j) { double dx = x[i] - x[j]; double dy = y[i] - y[j]; return sqrt(dx*dx + dy *dy); } /** * Process a single dataset for the problem. * Return true if successful. Return false if we encounter the * end of input marker or an unreocverable I/O error, */ bool processDataSet (istream& in) { int N; in >> N; if (N == 0) return false; for (int i = 0; i < N; ++i) { in >> x[i] >> y[i]; connected[i] = false; distanceFromConnectedNodes[i] = dist(i,0);; } connected[0] = true; double sum = 0.0; int numConnected = 1; int lastConnection = 0; while (numConnected < N) { // Update distances based on last connection int closestNode = -1; double closestDist = 0.0; for (int i = 0; i < N; ++i) { if (!connected[i]) { double d = dist(lastConnection, i); distanceFromConnectedNodes[i] = min(distanceFromConnectedNodes[i], d); if (closestNode < 0 || distanceFromConnectedNodes[i] < closestDist) { closestDist = distanceFromConnectedNodes[i]; closestNode = i; } } } //cerr << "Adding connection from " << lastConnection << " to " << closestNode << endl; sum += closestDist; lastConnection = closestNode; connected[closestNode] = true; ++numConnected; } cout << setprecision(2) << fixed << sum << endl; return true; } void undergroundCables (istream& in) { bool finished = false; while (!finished) { finished = !processDataSet(in); } } int main (int argc, char** argv) { // Program should normally read from standard in. But // for debugging purposes, it is sometimes easier to // give a file name on the command line. if (argc > 1) { ifstream in (argv[1]); undergroundCables (in); } else undergroundCables(cin); return 0; }