#include #include #include #include #include #include #include using namespace std; struct POS { double x, y, z; double Distance(const POS& rh)const{ return sqrt((x - rh.x) * (x - rh.x) + (y - rh.y) * (y - rh.y) + (z - rh.z) * (z - rh.z)); } }; struct SPHERE { POS p; double r; }; const double EPSIRON = 0.000000001; int CONNECT[100][100]; int VISITED[100]; bool DFS(int from, int to, const vector >& graph) { if (VISITED[from]){ return false; } VISITED[from] = true; if (CONNECT[from][to] || from == to){ return true; } const vector& nodes = graph[from]; for (vector::const_iterator it = nodes.begin(); it != nodes.end(); ++it){ if (DFS(*it, to, graph)){ CONNECT[*it][to] = true; CONNECT[to][*it] = true; CONNECT[from][to] = true; CONNECT[to][from] = true; CONNECT[*it][from] = true; CONNECT[from][*it] = true; return true; } } return false; } bool IsConnected(int from, int to, const vector >& graph) { memset(VISITED, 0, sizeof(VISITED)); return DFS(from, to, graph); } main() { int n; while (cin >> n && n){ SPHERE v[n]; vector > graph(n); memset(CONNECT, 0, sizeof(CONNECT)); multimap > open; for (int i = 0; i < n; ++i){ SPHERE& s = v[i]; cin >> s.p.x >> s.p.y >> s.p.z >> s.r; //cerr << s.p.x << " " << s.p.y << " " << s.p.z << " " << s.r; for (int j = 0; j < i; ++j){ double d = v[i].p.Distance(v[j].p); double f = d - v[i].r - v[j].r; if (f > - EPSIRON){ open.insert(make_pair(f, make_pair(i, j))); //cerr << f << " " << i << " " << j << endl;; //dist[i][j] = dist[j][i] = f; } else { graph[i].push_back(j); graph[j].push_back(i); CONNECT[i][j] = true; CONNECT[j][i] = true; //cerr << i << " " << j << endl; } } } //cerr << "hoge" << endl; bool is_ok = true; for (int i = 1; i < n; ++i){ is_ok &= IsConnected(0, i, graph); } if (is_ok){ printf("0.000\n"); continue; } double answer = 0.0; is_ok = false; while (!is_ok){ double d = open.begin()->first; int from = open.begin()->second.first; int to = open.begin()->second.second; open.erase(open.begin()); //cerr << d << " " << from << " " << to << endl; if (IsConnected(from, to, graph)){ continue; } CONNECT[from][to] = true; CONNECT[to][from] = true; graph[from].push_back(to); graph[to].push_back(from); //cerr << "hoge" << endl; answer += d; is_ok = true; for (int i = 1; i < n; ++i){ is_ok &= IsConnected(0, i, graph); } } printf("%.03lf\n", answer); } }