目录
- $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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/601888.html