题解

#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;
}