40pts求条
查看原帖
40pts求条
999574
Life_Game楼主2025/1/14 08:58
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e3+10;

int fa[N], n, h, r;

struct ball{
	int x, y, z, num;
}a[N];

vector<int>f1, f2;
int find(int x){
    if (x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}

void uni(int x, int y){
	fa[x] = find(y);
}

bool connect(int x, int y){
	return find(x) == find(y);	
}

double getDistance(ball x, ball y){
	return pow(x.x-y.x,2)+pow(x.y-y.y,2)+pow(x.z-y.z,2);	
}

bool getBorderDistance(ball x, bool isUpperBoder){
	if(isUpperBoder){
		return (x.z+r)>=h;
	}
	return (x.z-r)<=0;
}

bool isIntersect(ball x, ball y){
	if(getDistance(x, y)<=4*r*r){
		return 1;
	}
	return 0;
}

void init(){
	memset(a, 0, sizeof a);
	memset(fa, 0, sizeof fa);
	f1.clear(), f2.clear();
	for(int i=1;i<=n;i++){
		fa[i] = i;
	}
}

void solve(){
	cin>>n>>h>>r;
	init();
	for(int i=1;i<=n;i++){
		int x, y, z;cin>>x>>y>>z;
		a[i].x=x,a[i].y=y,a[i].z=z,a[i].num=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(isIntersect(a[i],a[j])){
				uni(a[i].num,a[j].num);
			} 
		}
		if(getBorderDistance(a[i],1)){
			f1.push_back(a[i].num);
		}
		if(getBorderDistance(a[i],0)){
			f2.push_back(a[i].num);
		}
	}
	for(auto i : f1){
		for(auto j : f2){
			if(connect(i, j)){
				cout<<"Yes"<<'\n';
				return ;
			}
		}
	}
	cout<<"No"<<'\n';
}
signed main(){	
	int T;
	cin>>T;
	while(T--) solve();
} 
2025/1/14 08:58
加载中...