// 01:33-2:06 #include #include #include #include #include #define EPS 1.e-5 #define LE(x, y) ((x) - (y) < EPS) using namespace std; typedef valarray xyz; typedef vector > adj_matrix; struct station{ xyz p; double r; station(){} station(const xyz &p, double r):p(p), r(r){} }; double infty = 9999999999.; double prim(adj_matrix &m){ int N = m.size(); if(N <= 1) return 0.; set tobeadded; for(int i = 1; i < N; i++){ tobeadded.insert(i); } int lastadded = 0; vector distances(N, infty); double totalweight = 0.; for(int i = 0; i < N - 1; i++){ double distmin = infty; int next = -1; for(set::iterator it = tobeadded.begin(); it != tobeadded.end(); ++it){ double &distnow = distances[*it]; if(m[lastadded][*it] < distnow){ distnow = m[lastadded][*it]; } if(distnow < distmin){ distmin = distnow; next = *it; } } if(distmin == infty){ break; } totalweight += distances[next]; tobeadded.erase(next); lastadded = next; } return totalweight; } int main(void){ int N; while(cin >> N && N){ vector stations; for(int i = 0; i < N; i++){ xyz p(3); double r; cin >> p[0] >> p[1] >> p[2] >> r; stations.push_back(station(p, r)); } adj_matrix distance(N, vector(N, 0.)); for(int i = 0; i < stations.size(); i++){ distance[i][i] = infty; for(int j = i + 1; j < stations.size(); j++){ xyz diff = stations[i].p - stations[j].p; double norm = (diff*diff).sum(); double abs_ = sqrt(norm) - stations[i].r - stations[j].r; if(LE(abs_, 0.)) abs_ = 0.; distance[i][j] = abs_; distance[j][i] = abs_; } } printf("%.3f\n", prim(distance)); } return 0; }