P3958 题解

· · 题解

题目传送门

思路

可以使用并查集解决此题。

首先将满足 z\ge h-r 的数放入集合 F_1 中，将满足 z\le r 的数放入集合 F_2 中。这是因为以上两个条件分别能满足顶面相交和底面相交。

然后判断两个空洞是否相通，只需判断 \text{dist}(P_i,P_j)\le2\times r 即可。这是因为两圆的圆心距离小于或等于它们的半径之和，两个圆就会相交或刚好相接。如果满足条件，就将 P_i 和 P_j 通过并查集合并。

最后，判断是否存在 F_{1,i} 与 F_{2,j} 相连即可。

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define y1 y_1
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e6+10;
int n,h,r,fa[N],x[N],y[N],z[N],f1[N],f2[N];
void _init(){
    for(int i=1;i<=n;++i)
        fa[i]=i;
    return;
}
int _find(int x){
    if(x==fa[x])
        return x;
    fa[x]=_find(fa[x]);
    return fa[x];
}
void _merge(int x,int y){
    int fx=_find(x),fy=_find(y);
    if(fx!=fy)
        fa[fx]=fy;
    return;
}
int dis(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);
}
void solve(){
    n=read(),h=read(),r=read();
    _init();
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;++i){
        x[i]=read(),y[i]=read(),z[i]=read();
        if(z[i]>=h-r)
            f1[++cnt1]=i;
        if(z[i]<=r)
            f2[++cnt2]=i;
        for(int j=1;j<=i;++j){
            if(dis(x[i],x[j],y[i],y[j],z[i],z[j])>4*r*r)
                continue;
            int temp_1=_find(i),temp_2=_find(j);
            if(temp_1!=temp_2)
                _merge(temp_1,temp_2);
        }
    }
    bool flag=false;
    for(int i=1;i<=cnt1;++i){
        for(int j=1;j<=cnt2;++j)
            if(_find(f1[i])==_find(f2[j])){
                flag=true;
                break;
            }
        if(flag)
            break;
    }
    printf(flag?"Yes\n":"No\n");
    return;
}
signed main(){
    short T=read();
    while(T--)
        solve();
    return 0;
}