洛谷 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;
}

原文链接:https://www.cnblogs.com/poi-bolg-poi/p/11519948.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有