30pts求调,过#1#2#4(附#3数据
查看原帖
30pts求调,过#1#2#4(附#3数据
359154
HIMkythen楼主2024/7/16 11:46
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
int t,n,h,r;
long long x[MAXN+1],y[MAXN+1],z[MAXN+1];
int a[MAXN+1];
long long 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 x){
	if(x==a[x]) return a[x];
	else{
		return a[x]=find(a[x]);
	}
}
void group(int p,int q){
    if(find(p)!=find(q)) a[find(q)]=find(p);
}
int main(){
	cin>>t;
	for(int k=0;k<t;k++){
		cin>>n>>h>>r;
		a[0]=0;
		a[MAXN]=MAXN;
		for(int i=1;i<=n;i++){
			a[i]=i;
		}
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i]>>z[i];
			if(z[i]-r<=0){
				group(i,0);
			}
			if(z[i]+r>=h){
				group(i,MAXN);
			}
			for(int j=1;j<=n;j++){
				if(dis(x[i],y[i],z[i],x[j],y[j],z[j])<=4*r*r){
					group(i,j);
					//cout<<i<<" "<<j<<endl;
				}
			}
		}
		if(find(0)==find(MAXN)){
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
		
	}
	return 0;
}

#3数据: in:https://www.luogu.com.cn/paste/meohc542 out:https://www.luogu.com.cn/paste/meohc542

2024/7/16 11:46
加载中...