用的并查集

#include<bits/stdc++.h>
#define int long long
using namespace std;

int t;
int n,h;
int r;
int x[101010],y[101010],z[101010];
int fa[1010];
bool top[1010],dow[1010];//表示当前集合中是否有与顶部或底部相连的洞

bool touch(int a,int b){//判断连同
	long long dist;
	dist=pow(x[a]-x[b],2)+pow(y[a]-y[b],2)+pow(z[a]-z[b],2);
	if(dist<=4*r*r)
		return true;
	return false;
}

int find(int x){//寻找祖先节点并更新top和dow的值
	if(x==fa[x])
		return x;
	int f=find(fa[x]);
	if(top[f])
		top[x]=true;
	if(dow[f])
		dow[x]=true;
	fa[x]=f;
}

signed main(){
	cin>>t;
	while(t--){
		memset(fa,0,sizeof(fa));
		memset(dow,false,sizeof(dow));
		memset(top,false,sizeof(top));
		cin>>n>>h>>r;
		for(int i=1;i<=1000;i++)
			fa[i]=i;
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i]>>z[i];
			if(z[i]<=r)
				dow[i]=true;
			if(h-z[i]<=r)
				top[i]=true;
//			cout<<top[i]<<" "<<dow[i]<<endl;
		}
		bool check=true;
		for(int i=1;i<=n;i++){
			for(int j=i;j<=n;j++){
//				cout<<touch(i,j)<<endl;
				if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])>4*r*r) 
					continue;
				if(touch(i,j)){
					int fx=find(i),fy=find(j);
					if(fx!=fy){
						if(dow[fa[fx]])
							dow[fy]=true;
						if(top[fa[fx]])
							top[fy]=true;
						fa[fx]=fy;
					}
//					cout<<fa[fx]<<" "<<fa[fy]<<endl;
				}
				if(fa[i]==fa[j]&&dow[fa[i]]&&top[fa[i]]){
					cout<<"Yes";
					check=false;
					break;
				}
//				cout<<i<<" "<<j<<" "<<zx[i]<<" "<<zx[j]<<" "<<dow[zx[i]]<<" "<<top[zx[i]]<<endl;
			}
			if(!check)
				break;
		}
		if(check)
			cout<<"No";
		cout<<endl;
	}
	return false;
}