#include<iostream> #include<math.h> using namespace std; int fa[1000000]; long long x[100000],y[100000],z[100000]; int vis[100000]={0};long long n,h,r; int64_t dis(long long x,long long y,long long z,long long x1,long long y1,long long z1){ return (x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1); } int find(int s) { if(s==fa[s]) return s; else return fa[s]=find(fa[s]); } int Union(int x,int y)//合并时选择z轴的值大的那个作为共同的父亲 { if(find(x)==find(y)) return 0; else if(z[find(y)]<z[find(x)]) fa[find(y)]=find(x); else fa[find(x)]=find(y); return 1; } void dfs(int xx)//遍历所有连通的点 {vis[xx]=1; for(int i=1;i<=n;i++) { if(dis(x[xx],y[xx],z[xx],x[i],y[i],z[i])<=4*r*r&&!vis[i]) { vis[i]=1; Union(xx,i); dfs(i); } } } int main() { int T; cin>>T; while(T--) { int key=0; scanf("%lld%lld%lld",&n,&h,&r); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&x[i],&y[i],&z[i]); for(int i=1;i<=n;i++) if(vis[i]==0) dfs(i); for(int i=1;i<=n;i++) if(z[i]-r<=0&&z[fa[i]]+r>=h) { key=1;break; } if(key) cout<<"Yes"<<endl; else cout<<"No"<<endl; for(int i=1;i<=n;i++) vis[i]=0; } return 0; }
全部评论
(0) 回帖