#创作计划# 新思路（并查集）

针对于每一个空洞我们定义：
最大高度 $=$ 球心高度 $+$ 该球半径，表示在这个球内所能到达的最高的高度；
最小高度 $=$ 球心高度 $-$ 该球半径，表示在这个球内所能到达的最矮的高度。

当两个空洞 $P_1(x_1,y_1,z_1)$、$P2(x_2,y_2,z_2)$ 相切或是相交时，一定满足（如题所述）：

$$\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$$

为避免精度问题，两边平方（去根号）得

$$(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2 \le 4 \times r^2$$

此时便可更新 最大高度 和 最小高度，使用并查集合并，具体操作见代码。
最后只需查看是否存在一个空洞使得其 最大高度 $\ge h$, 最小高度 $\le 0$ 即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long//十年OI一场空，不开____一场空
int n, h, r, t;//如题目
struct Node {
	int x, y, z;
} a[1001];//空洞节点
int fa[1002], min_h[1002], max_h[1002];
//fa是父亲编号，min_h是最小高度，max_h是最大高度
int dist(int x1, int x2, int y1, int y2, int z1, int z2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2);
}
int find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}//并查集函数
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> h >> r;
		for (int i = 1; i <= n; i++) {
			cin >> a[i].x >> a[i].y >> a[i].z;
          //初始化 fa，min_h 和 max_h
			fa[i] = i;
			min_h[i] = a[i].z - r;
			max_h[i] = a[i].z + r;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				if (4 * r * r >= dist(a[i].x, a[j].x, a[i].y, a[j].y, a[i].z, a[j].z)) {
					int ri = find(i), rj = find(j);
					fa[rj] = ri;//合并
          //更新 min_h 和 max_h
					min_h[ri] = min(min_h[ri], min_h[rj]);
					max_h[ri] = max(max_h[ri], max_h[rj]);
				}
			}
		}
		bool flag = 0;
		for (int i = 1; i <= n; i++) {
			if (fa[i] != i) continue;
			if (min_h[i] <= 0 && max_h[i] >= h) {//见上
				flag = 1;
				break;
			}
		}
		if (flag) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}