如题

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

ll n , h , r ;
int f[1001];

struct poi{
	ll x;
	ll y;
	ll z;
};

//排序
bool cmp(struct poi a , struct poi b){
	if(a.z!=b.z)return a.z<b.z;
	if(a.y!=b.y)return a.y<b.y;
	return a.x<b.x;
}

//并查集
int find(int x){
	if(x!=f[x])f[x] = find(f[x]);
	return f[x];
}

//两个洞是否连接
bool qwq(struct poi a , struct poi b){
	return (a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y)+(a.z - b.z)*(a.z - b.z) <= 4*r*r;
}


void solve(){
	
	//读入n，h，r
	cin >> n >> h >> r;
	
	//读入每个洞+并查集初始化
	struct poi a[1005];
	
	for(int i = 0 ; i < n ; i++){
		cin >> a[i].x >> a[i].y >> a[i].z;
		f[i] = i;
	}
	
	//排序
	sort(a,a+n,cmp);
	
	int min = 0 ;//与底部相接的洞数
	int max = 0 ;//与顶部相接的洞数
	
	//统计与底部相接的洞数
	for(int i = 0 ; i < n ; i++){
		if(a[i].z-r<=0)min++;
		else break;
	}
	
	//统计与顶部相接的洞数
	for(int i = n-1 ; i >= 0 ; i--){
		if(a[i].z + r >= h)max++;
		else break;
	}
	
	//如果不存在与顶部或底部相接的洞，直接输出No
	if(min==0||max==0){
		cout << "No" << '\n';
		return;
	}
	
	//逐个遍历
	for(int i = 1 ; i < n ; i++){
		
		//逐个比较
		for(int j = i-1 ; j >= 0 ; j--){
			
			if(a[j].z+r < a[i].z-r)break;//因为是按照z递增排序所以dz>2r的就不用看了
			
			//如果能连接，改变并查集
			if(qwq(a[i],a[j])){
				int tem1 = find(f[i]);
				int tem2 = find(f[j]);
				if(tem1!=tem2)f[i] = tem2;
			}
		}
	}
	
	//在和顶部相交的洞里找有没有和与在底部相交的洞相交的
	for(int i = 1 ; i <= max ; i++){
		if(find(f[n-i])<min){
			cout << "Yes" <<'\n';
			return;
		}
	}
	cout << "No" <<'\n';
	return;
}

int main(){
	
	//关闭同步流
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t = 1;
	cin >> t;
	while(t--)solve();
	return 0;
}