| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
水过#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxv=100+5;
const int maxe=10000+5;
struct Edge{
int from,to;
double weight;
};
struct point{
double x,y,z,r;
};
bool operator<(const Edge &E1,const Edge &E2)
{
return E1.weight<E2.weight;
}
int parent[maxv];
point p[maxv];
Edge edges[maxe];
int find(int x)
{
return x==parent[x]?x:parent[x]=find(parent[x]);
}
int main()
{
int n;
while(scanf("%d",&n)==1&&n)
{
for(int i=0;i<n;i++)
cin>>p[i].x>>p[i].y>>p[i].z>>p[i].r;
for(int i=1;i<=n;i++)
parent[i]=i;
int cnt=0;
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
{
double k=(p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)+(p[i].z-p[j].z)*(p[i].z-p[j].z);
double k1=(p[i].r+p[j].r)*(p[i].r+p[j].r);
if(k<=k1) {
int p1=find(i+1);
int p2=find(j+1);
if(p1==p2) continue;
parent[p1]=p2;
}
else {
edges[cnt].from=i+1;
edges[cnt].to=j+1;
edges[cnt].weight=sqrt(k)-sqrt(k1);
cnt++;
}
}
sort(edges,edges+cnt);
double sum=0;
for(int i=0;i<cnt;i++)
{
int p1=find(edges[i].from);
int p2=find(edges[i].to);
if(p1==p2) continue;
parent[p1]=p2;
sum+=edges[i].weight;
}
printf("%.3f\n",sum);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator