洛谷 P3958 乳酪

目錄

• 題目
• 思路
• $Code$

題目

P3958 乳酪

思路

並查集。將乳酪的下錶面設為$0$號，輸入空洞位置時判斷該空洞如果與下錶面相切或相交就和到一個集合里，最後找到與上錶面相切或相交的空洞判斷與$0$號是否在一個集合里。

$Code$

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define MAXN 1001
#define rr register
#define int long long
using namespace std;
int t,n,h,r,fa[MAXN];
int x[MAXN],y[MAXN],z[MAXN];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void read(int &T){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    T=f?-x:x;
}
inline double dist(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])+(z[a]-z[b])*(z[a]-z[b]));
}

signed main(){
    read(t);
    while(t--){
        read(n),read(h),read(r);
        for(rr int i=0;i<=MAXN;++i) fa[i]=i;
        for(rr int i=1;i<=n;++i){
            read(x[i]),read(y[i]),read(z[i]);
            if(z[i]-r<=0){
                fa[i]=0;
            }
        }
        for(rr int i=1;i<=n;++i){
            for(rr int j=1;j<=n;++j){
                if(find(i)!=find(j)&&dist(i,j)<=(2*r)){
                    fa[find(i)]=find(j);
                }
            }
        }
        bool f=0;
        for(rr int i=1;i<=n;++i){
            if(z[i]+r>=h&&find(0)==find(i)){
                puts("Yes");
                f=1;
                break;
            }
        }
        if(!f) puts("No");
    }
    return 0;
}