设为首页 加入收藏

TOP

洛谷 P3958 奶酪
2019-09-15 00:32:39 】 浏览:58
Tags:洛谷 P3958 奶酪

题目

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;
}
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇QRowTable表格控件(五)-重写表头.. 下一篇内联函数分析

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目