http://poj.org/problem?id=2031
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 7 const double eps=1e-8; 8 const int inf=1<<23; 9 int cmp(double x) 10 { 11 if(fabs(x)<eps) return 0; 12 if(x>0) return 1; 13 return -1; 14 } 15 16 const double pi=acos(-1.0); 17 inline double sqr(double x) 18 { 19 return x*x; 20 } 21 22 inline double Sqrt(double a) 23 { 24 return a<=0?0:sqrt(a); 25 } 26 27 struct point 28 { 29 double x,y,z,r; 30 point(){} 31 point(double a,double b,double c,double d):x(a),y(b),z(c),r(d){} 32 }; 33 34 double dis(const point &a,const point &b) 35 { 36 return Sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)+sqr(a.z-b.z)); 37 } 38 39 double dist[1000]; 40 double diss[110][110],ans; 41 bool vis[1000]; 42 bool prime(int n) 43 { 44 memset(vis,0,sizeof(vis)); 45 for(int i=1; i<=n; i++) 46 dist[i]=inf; 47 ans=0;dist[1]=0; 48 for(int i=1; i<=n; i++){ 49 double temp=inf; 50 int k=0; 51 for(int j=1; j<=n; j++) 52 { 53 if(!vis[j]&&dist[j]<temp) 54 { 55 temp=dist[j]; 56 k=j; 57 } 58 } 59 if(temp==inf) return false; 60 vis[k]=true; 61 ans+=temp; 62 for(int j=1; j<=n; j++) 63 { 64 if(!vis[j]&&dist[j]>diss[k][j]) 65 { 66 dist[j]=diss[k][j]; 67 } 68 } 69 } 70 return true; 71 } 72 int main() 73 { 74 int n; 75 while(scanf("%d",&n)&&n) 76 { 77 point a[1000]; 78 memset(diss,0,sizeof(diss)); 79 for(int i=1; i<=n; i++) 80 { 81 scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r); 82 } 83 memset(diss,0,sizeof(diss)); 84 for(int i=1; i<=n; i++) 85 { 86 for(int j=1; j<=n; j++) 87 { 88 if(dis(a[i],a[j])-a[i].r-a[j].r<=0) 89 diss[i][j]=0; 90 else if(dis(a[i],a[j])-a[i].r-a[j].r>eps) 91 diss[i][j]=dis(a[i],a[j])-a[i].r-a[j].r; 92 } 93 } 94 prime(n); 95 printf("%.3lf ",ans); 96 } 97 return 0; 98 }