题目

分析

使用并查集
如果两个洞相交（或相切），就把它们连入一个集合
最后判断每一条通道是否存在元素与底部、顶部相连即可。如果都有，那么输出 Yes。

易错点

最后要判断每一条通道
因为只要有一条能从底部到顶部的，就代表能到了
其他易错点见代码的备注

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

typedef long long ll;//记得开ll
const int N=1e3+7;
ll p[N];
int t;
ll n,h;
ll r;


ll x[N],y[N],z[N];//用数组计数，偏的数据结构别用，不然会导致错误
set<ll> s;
ll  lst[N];
ll  hst[N];
ll find(ll  x)
{
    if(p[x]!=x) return find(p[x]);
    else return p[x];
}
bool reachable(ll  x1,ll  y1,ll  z1,ll x2,ll y2,ll z2)
{
    double dist;
    dist=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
    //printf("%lf %d\n",dist,r);
    if(dist<=(double)2*r) return true;
    else return false;
}
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&h,&r);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
            p[i]=i;
            for(int k=1;k<i;k++){
                if(reachable(x[i],y[i],z[i],x[k],y[k],z[k])){
                    p[find(k)]=p[find(i)];
                }
            }
        }
        //把所有祖宗节点存到s中
        for(int i=1;i<=n;i++) s.insert(find(i));
        for(int i=1;i<=N;i++) lst[i]=1e9+7;
        for(int i=1;i<=N;i++) hst[i]=-1;
        //遍历一遍vec，找到所有idx的最大z和最小z
        for(int i=1;i<=n;i++){
            ll parent=find(i);
            lst[parent]=min(lst[parent],z[i]-r);
            hst[parent]=max(hst[parent],z[i]+r);
        }
        int flag=0;
        for(auto i:s){
            if(lst[i]<=0&&hst[i]>=h){
                flag=1; break;
            }
        }
        if(flag==1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}