//
#include<iostream>
#include<cmath>
using namespace std;
struct BALL
{
double x,y,z,r;
};
struct Edge
{
int x,y;
double w;
};
BALL ball[200];
Edge edge[10000];
int parent[200];
int n;
int find(int c)
{
if(parent[c]<0) return c;
else return find(parent[c]);
}
bool uni(int x,int y)
{
int a,b,t;
a=find(x);
b=find(y);
if(a!=b)
{
t=parent[a]+parent[b];
if(parent[a]<parent[b])
{
parent[b]=a;
parent[a]=t;
}
else
{
parent[a]=b;
parent[b]=t;
}
return true;
}
return false;
}
double Kruskal(int en)
{
int i;
double mst=0;
memset(parent,-1,sizeof(parent));
for(i=0;i<en;i++)
if(uni(edge[i].x,edge[i].y))
mst+=edge[i].w;
return mst;
}
int cmp(const void *a, const void *b)
{
double ta=(*(Edge*)a).w,tb=(*(Edge*)b).w;
if(ta<tb) return -1;
else if(ta==tb) return 0;
else return 1;
}
int main()
{
int i,j,k;
double dx,dy,dz,ts;
while(scanf("%d",&n)!=EOF && n)
{
for(i=0;i<n;i++)
scanf("%lf%lf%lf%lf",&(ball[i].x),&(ball[i].y),&(ball[i].z),&(ball[i].r));
for(i=0,k=0;i<n;i++)
for(j=i+1;j<n;j++)
{
edge[k].x=i;
edge[k].y=j;
dx=ball[i].x-ball[j].x;
dy=ball[i].y-ball[j].y;
dz=ball[i].z-ball[j].z;
ts=pow(dx*dx+dy*dy+dz*dz,0.5);
if(ts>ball[i].r+ball[j].r)
edge[k++].w=ts-ball[i].r-ball[j].r;
else edge[k++].w=0;
}
qsort(edge,k,sizeof(edge[0]),cmp);
printf("%.3lf\n",Kruskal(k));
}
}posted on 2009-07-29 10:05
wyiu 閱讀(164)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ