针对于每一个空洞我们定义:
最大高度 === 球心高度 +++ 该球半径,表示在这个球内所能到达的最高的高度;
最小高度 === 球心高度 −-− 该球半径,表示在这个球内所能到达的最矮的高度。
当两个空洞 P1(x1,y1,z1)P_1(x_1,y_1,z_1)P1 (x1 ,y1 ,z1 )、P2(x2,y2,z2)P2(x_2,y_2,z_2)P2(x2 ,y2 ,z2 ) 相切或是相交时,一定满足(如题所述):
dist(P1,P2)=(x1−x2)2+(y1−y2)2+(z1−z2)2≤2×r\mathrm{dist}(P_1,P_2)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} \le 2 \times r dist(P1 ,P2 )=(x1 −x2 )2+(y1 −y2 )2+(z1 −z2 )2 ≤2×r
为避免精度问题,两边平方(去根号)得
(x1−x2)2+(y1−y2)2+(z1−z2)2≤4×r2(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2 \le 4 \times r^2 (x1 −x2 )2+(y1 −y2 )2+(z1 −z2 )2≤4×r2
此时便可更新 最大高度 和 最小高度,使用并查集合并,具体操作见代码。
最后只需查看是否存在一个空洞使得其 最大高度 ≥h\ge h≥h, 最小高度 ≤0\le 0≤0 即可。