C - Building a Space Station

题目链接：

题目：

您是空间站工程团队的成员，并在该站的施工过程中分配了一项任务。您需要编写一个计算机程序来完成任务。

空间站由许多单元组成，称为单元。所有细胞都是球形的，但它们的大小不一定是均匀的。在该站成功进入其轨道后不久，每个小区固定在其预定位置。很奇怪，两个细胞可能彼此接触，甚至可能重叠。在极端情况下，细胞可能完全包围另一个细胞。我不知道这样的安排是如何可能的。

所有细胞必须连接，因为机组成员应该能够从任何细胞走到任何其他细胞。如果，（1）A和B相互接触或重叠，（2）A和B通过“走廊”连接，或者（3）有一个单元格C，它们可以从单元格A走到另一个单元格B.从A到C，从B到C都是可能的。注意，条件（3）应该被传递解释。

您需要设计一个配置，即哪些单元格对与走廊连接。走廊配置有一些自由。例如，如果存在三个单元A，B和C，彼此不接触或不重叠，则至少三个计划是可能的，以便连接所有三个单元。第一个是建造走廊A-B和A-C，第二个是B-C和B-A，第三个是C-A和C-B。建造走廊的成本与其长度成正比。因此，您应该选择走廊总长度最短的计划。

您可以忽略走廊的宽度。在两个单元格表面上的点之间构建一个走廊。它可以任意长，但当然选择最短的一个。即使两个走廊A-B和C-D在空间相交，也不认为它们在（例如）A和C之间形成连接路径。换句话说，您可以认为两条走廊从不相交。

输入

输入由多个数据集组成。每个数据集以下列格式给出。

x1 y1 z1 r1

x2 y2 z2 r2

...

xn yn zn rn

数据集的第一行包含整数n，即整数。 n是正数，不超过100。

以下n行是细胞的描述。一行中的四个值是球体的中心的x，y和z坐标，以及球体中的半径（在问题的其余部分中称为r），按此顺序。每个值由小数部分给出，小数点后3位。值由空格字符分隔。

x，y，z和r中的每一个都是正的并且小于100.0。

输入的结尾由包含零的线表示。

产量

对于每个数据集，应打印走廊的最短总长度，每个都在一个单独的行中。打印的值应在小数点后3位。它们可能没有大于0.001的误差。

请注意，如果不需要走廊，也就是说，如果所有单元都没有走廊连接，则走廊的最短总长度为0.000。

样本输入

10.000 10.000 50.000 10.000

40.000 10.000 50.000 10.000

40.000 40.000 50.000 10.000

30.000 30.000 30.000 20.000

40.000 40.000 40.000 20.000

5.729 15.143 3.996 25.837

6.013 14.372 4.818 10.671

80.115 63.292 84.477 15.120

64.095 80.924 70.029 14.881

39.472 85.116 71.369 5.553

样本输出

20.000

0.000

73.834

思路：

在三维空间中给你 n 个球体的坐标和半径

如果这些球体间没有相通,则需要你去建立一些通道把所有的球体连接起来。

表面相切即可认为相通。

首先在各球体间建图,然后再按照边从小到大排序

用并查集查找两点是否属于同一联通分量【即判断这条边的两个球是否相通】

如果不属于同一联通分量，则连接即可

由于每次都是找的最短的边,所以最终所求一定是最短距离了

//// Created by hy on 2019/7/30.//#include
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include
           
            using namespace std;typedef long long ll;const int maxn=2e5+10;int n,m;struct Node{ double x,y,z,r;}node[maxn];struct Edge{ int u,v; double w; bool operator<(const Edge &other)const{ return this->w

转载于:https://www.cnblogs.com/Vampire6/p/11272860.html

你可能感兴趣的文章

2-sat 问题【例题 Flags（2-sat+线段树优化建图）】