Description
共 $T$ 组数据。在一个三维坐标系上,有 $n$ 个球体,坐标分别为 $(x_i, y_i, z_i)$,半径为 $r$ 。现在从 $z$ 轴的 $0$ 位置出发,所经过的位置一定要有球体覆盖,求能否到达 $z$ 轴的 $h$ 位置。
$(1 \leq n \leq 10^3,1 \leq h,r \leq 10^9,T \leq 20$,坐标的绝对值不超过 $10^9)$
Source
Solution
考虑用 并查集 维护球体形成的连通块。
如何判断两个球体是否连通?
这就要用到三维空间中的欧式距离公式:
若两个球体球心之间的欧式距离 $|AB| \leq 2r$,则说明这两个球体相交或者相切,可以把它们合并到同一个连通块中。
对于每个连通块,如果与底面和顶面都相连,就能够到达,反之则不行。时间复杂度为 $O(n^2)$ 。
由于求欧式距离时存在精度误差,我们可以将不等式两边开平方,得到
Code
1 |
|