Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
ACM ICPC 2018 World Finals

水过

Posted by ALLACS at 2018-01-08 15:30:05 on Problem 2031
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator