并查集维护相切/相交的空洞，上下表面挂虚拟节点，平方比较后判断是否同根。
OJ: roj
题目 ID: 3651
难度:普及
标签:并查集图论连通性python
创建: 2026-10-02 12:59
更新: 2026-10-07 13:50
题目描述
一块高度为
输入输出见 problem.md，数据范围
思路
把每个空洞看成节点，相切/相交就连边，上下表面分别作为虚拟节点。用整数平方比较避免浮点误差；按
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 13:00
# update_at: 2026-10-02 13:00
import sys
def find(fa: list[int], x: int) -> int:
"""并查集查根：路径压缩，把沿途节点直接挂到根上。"""
while fa[x] != x:
fa[x] = fa[fa[x]]
x = fa[x]
return x
def union(fa: list[int], a: int, b: int) -> None:
"""把 a、b 所属的连通块合并成一个。"""
ra, rb = find(fa, a), find(fa, b)
if ra != rb:
fa[rb] = ra
def can_escape(holes: list[tuple[int, int, int]], h: int, r: int) -> bool:
"""能否借助相切/相交的空洞从下表面走到上表面。
最后两个元素是虚拟节点，分别代表下表面与上表面；两球相切或相交
等价于球心距离不大于 2r，用平方比较避免开方。
"""
holes.sort(key=lambda hole: hole[2]) # 按 z 升序，方便只检查 z 窗口内的球对
bottom, top = len(holes), len(holes) + 1
fa = list(range(len(holes) + 2))
reach, link = 2 * r, 4 * r * r # 球心 z 差上限、球心距离平方上限
for i, (x, y, z) in enumerate(holes):
if z <= r: # 与下表面 z = 0 相交或相切
union(fa, bottom, i)
if z + r >= h: # 与上表面 z = h 相交或相切
union(fa, top, i)
for i, (x1, y1, z1) in enumerate(holes):
for j, (x2, y2, z2) in enumerate(holes[i + 1:], i + 1):
if z2 - z1 > reach: # 已排序，后面的球 z 只会更大，窗口到头了
break
if (x1 - x2) ** 2 + (y1 - y2) ** 2 + (z1 - z2) ** 2 <= link:
union(fa, i, j)
return find(fa, bottom) == find(fa, top)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
T = next(data)
for _ in range(T):
n, h, r = next(data), next(data), next(data)
holes = [(next(data), next(data), next(data)) for _ in range(n)] # n 个球心
out.append('Yes' if can_escape(holes, h, r) else 'No')
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 16:01
* update_at: 2026-10-06 16:01
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1005; // n <= 1000
struct Hole {
ll x, y, z;
} a[MAXN]; // 按 z 排序后的球心
int fa[MAXN + 2]; // 并查集父节点，额外 2 个给下表面和上表面
int find_root(int x) {
int r = x;
while (fa[r] != r) r = fa[r];
while (fa[x] != x) {
int p = fa[x];
fa[x] = r;
x = p;
}
return r;
}
void unite(int x, int y) {
int rx = find_root(x);
int ry = find_root(y);
if (rx != ry) fa[ry] = rx;
}
bool cmp_z(const Hole &p, const Hole &q) {
return p.z < q.z;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
ll h, r;
cin >> n >> h >> r;
for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y >> a[i].z;
sort(a, a + n, cmp_z); // 按 z 升序，用于 z 窗口剪枝
int bottom = n;
int top = n + 1;
for (int i = 0; i < n + 2; i++) fa[i] = i;
for (int i = 0; i < n; i++) {
if (a[i].z <= r) unite(bottom, i); // 与下表面相连
if (a[i].z + r >= h) unite(top, i); // 与上表面相连
}
ll reach = 2 * r; // 球心 z 差超过 2r 不可能相交
__int128 limit = (__int128)4 * r * r; // 球心距离平方上限
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[j].z - a[i].z > reach) break; // z 差已经太大，后面更大
__int128 dx = a[j].x - a[i].x;
__int128 dy = a[j].y - a[i].y;
__int128 dz = a[j].z - a[i].z;
__int128 dist2 = dx * dx + dy * dy + dz * dz;
if (dist2 <= limit) unite(i, j);
}
}
cout << (find_root(bottom) == find_root(top) ? "Yes" : "No") << '\n';
}
return 0;
}