#include #include #include #include #include #include #include using namespace std; typedef double weighttype; const double weightmax = 9999999999.; typedef int point; typedef pair edge; typedef vector edges; typedef map graph; weighttype prim(graph &g) { set V; int Vsize; set U; for(graph::iterator git = g.begin() ; git != g.end() ; git++){ V.insert(git->first); edges eds = git->second; sort(eds.begin(),eds.end()); git->second = eds; } Vsize = V.size(); if(Vsize < 2) return 0; U.insert(*(V.begin())); V.erase(*(V.begin())); weighttype alldistance = 0.; while(U.size() != Vsize){ weighttype nowmin = weightmax; point nowdest; point nowfrom; for(set::iterator from = U.begin() ; from != U.end() ; from++){ edges eds = g[*from]; for(int t = 0 ; t < eds.size() ; t ++){ if(eds[t].first > nowmin) break; if(U.count(eds[t].second) >0){ continue; }else if(eds[t].first < nowmin){ nowfrom = *from; nowmin = eds[t].first; nowdest = eds[t].second; if(eds[t].first < 0.0000001){ goto loopend; } break; } break; } } loopend: if(nowmin == weightmax){ cout << "error" << endl; return weightmax; } V.erase(nowdest); U.insert(nowdest); alldistance += nowmin; } return alldistance; } struct location{ double x; double y; }; int main(void){ int n; graph g; vector locs; cin >> n; g.clear(); locs.clear(); int i; for( i = 0 ; i < n ; i++){ location aLoc; cin >> aLoc.x >> aLoc.y; locs.push_back(aLoc); } for(i = 0 ; i < locs.size() ; i ++){ for(int t = 0 ; t < locs.size() ; t++){ double distance = sqrt( (locs[i].x-locs[t].x)*(locs[i].x-locs[t].x) + (locs[i].y-locs[t].y)*(locs[i].y-locs[t].y)); g[i].push_back(edge(distance,t)); } } weighttype res = prim(g); printf("%.3f\n",res); }