Problem4063--莫瑞亚矿坑

4063: 莫瑞亚矿坑

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

矮人族在莫瑞亚矿坑寻找他们的秘密矿藏——秘银。

他们在莫瑞亚的地下矿井中有n处工地,第i(1<=i<=n)个工地的坐标为(Xi,Yi,Zi),我们可以把工地形状想象成球形,并且半径为Ri。若在两处工地间修建一条通路,那么最短的路径长度为两个工地之间的直线距离。下图红色线段部分。若两个球形有重合部分,那么其间路径长度计为0。

现在矮人之王索林一世希望你能帮他计算让所有矿坑间都有路径联通最少需要开凿多长的距离。假设最开始没有路径。

Input

输入包含多组测试数据,每组测试数据第一行为一个整数n(2<=n<=3000)代表工地个数,接下来为n行,每行为4个实数,分别为 Xi Yi Zi Ri,其中(Xi,Yi,Zi)为工地坐标,Ri为工地半径0<=Xi,Yi,Zi<=1000, 1<=Ri<=10。
当n为0时输入结束。

Output

输出一行,为最少开凿路径的长度,结果保留三位小数。

Sample Input Copy

2
98866.844 82035.455 64988.375 6.146
87994.513 87226.615 19636.699 2.202
2
10.000 10.000 10.000 20.000
20.000 20.000 20.000 20.000
4
87687.553 45914.171 98024.646 6.372
86922.318 15446.919 30342.421 5.996
72952.390 94569.830 92393.391 3.135
68366.641 76963.180 31109.910 4.980
0

Sample Output Copy

46916.382
0.000
179305.988

HINT

空间两点A(x1,y1,z1),B(x2,y2,z2)之间距离:

Source/Category