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