奶酪

主要用到了并查集，先遍历所有空洞，标记与上下表面连通的空洞，同时检查当前空洞与已遍历空洞的连通性，连通则合并； 遍历所有上表面连通空洞和下表面连通空洞，如果存在连通的结果就输出 Yes，否则输出 No。

#include<bits/stdc++.h>
using namespace std;

int f[1001];
int gf(int x) {
    if (x != f[x]) f[x] = gf(f[x]);
    return f[x];
}
// 计算球心距离平方
long long dis(long long x, long long y, long long z, long long x1, long long y1, long long z1) {
    return (x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1);
}
long long x[100001],y[100001],z[100001]; // 空洞球心坐标
int f1[100001],f2[100001]; //顶面底面连通空洞

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    int n,h; 
    long long r;
    for (int i=1;i<=t;i++){
        cin >> n >> h >> r;
        int tot1=0;//顶面
        int tot2=0;//底面
        // 并查集初始化
        for (int j=1;j<=n;j++){
          f[j]=j;
         }
        
        for (int j=1;j<=n;j++){
            cin >> x[j] >> y[j] >> z[j];   
            // 标记顶面连通空洞
            if (z[j]+r>=h){
                tot1++;
                f1[tot1]=j;
            }
            // 标记底面连通空洞
            if (z[j]-r<=0){
                tot2++;
                f2[tot2]=j;
            }
            // 合并连通的空洞
            for (int k=1;k<=j;k++){
            	if ((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])>4*r*r) continue;
                if (dis(x[j],y[j],z[j],x[k],y[k],z[k])<=4*r*r){
                    int a1=gf(j);
                    int a2=gf(k);
                    if (a1!=a2) f[a1]=a2;
                }
            }
        } 
        // 循环所有的上下空洞，判断是否连通上下表面
        int s=0;
        for (int j=1;j<=tot1;j++){
            for (int k=1;k<=tot2;k++){
                if (gf(f1[j])==gf(f2[k])){
                    s=1; 
                    break;
                }
            }
        }
        if (s==1) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}