1 /* 2 最小生成樹 + 幾何判斷 3 Kruskal 球心之間的距離 - 兩個球的半徑 < 0 則說明是覆蓋的！此時的距離按照0計算 4 */ 5 #include<iostream> 6 #include<cstdio> 7 #include<cstring> 8 #include<cmath> 9 #include<algorithm> 10 using namespace std; 11 int f[105]; 12 struct ball{ 13 double x, y, z, r; 14 }; 15 16 struct connect{ 17 double dist; 18 int a, b; 19 }; 20 21 connect c[5005]; 22 23 ball b[105]; 24 25 bool cmp(connect a, connect b){ 26 return a.dist < b.dist; 27 } 28 int n; 29 30 int getFather(int x){ 31 return x==f[x] ? x : f[x]=getFather(f[x]); 32 } 33 34 int Union(int a, int b){ 35 int fa=getFather(a), fb=getFather(b); 36 if(fa!=fb){ 37 f[fa]=fb; 38 return 1; 39 } 40 return 0; 41 } 42 43 int main(){ 44 int i, j; 45 while(scanf("%d", &n) && n){ 46 for(i=1; i<=n; ++i) 47 scanf("%lf%lf%lf%lf", &b[i].x, &b[i].y, &b[i].z, &b[i].r); 48 int cnt=0; 49 for(i=1; i<n; ++i) 50 for(j=i+1; j<=n; ++j){ 51 double d = sqrt((b[i].x-b[j].x)*(b[i].x-b[j].x) + (b[i].y-b[j].y)*(b[i].y-b[j].y) + (b[i].z-b[j].z)*(b[i].z-b[j].z)) 52 - (b[i].r + b[j].r); 53 c[cnt].dist= d<0 ? 0: d; 54 c[cnt].a=i; 55 c[cnt++].b=j; 56 } 57 sort(c, c+cnt, cmp); 58 double minSum=0.0; 59 for(i=1; i<=n; ++i) 60 f[i]=i; 61 for(i=0; i<cnt; ++i){ 62 if(Union(c[i].a, c[i].b)) 63 minSum+=c[i].dist; 64 } 65 printf("%.3lf\n", minSum); 66 } 67 return 0; 68 }
?
)
