Problem4057--莫瑞亚

4057: 莫瑞亚

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

Submit

Description

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

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

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

Input

输入包含多组测试数据,每组测试数据第一行为一个整数n(2<=n<=10000)代表工地个数,接下来为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
90573.257 62523.819 84782.893 8.648
99923.650 20812.228 36598.304 3.383
2
10.000 10.000 10.000 20.000
20.000 20.000 20.000 20.000
4
87675.469 16604.506 3484.482 7.920
30967.993 21231.668 83759.227 6.392
90399.243 57762.358 45395.678 6.561
65536.213 79504.857 27608.603 1.229
0

Sample Output Copy

64401.021
0.000
175896.421

HINT

空间两点距离:

Source/Category