80分玄关wa#7#8 开了long long
查看原帖
80分玄关wa#7#8 开了long long
1106763
wjc20230920楼主2024/5/16 19:24
#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N =200010;
int n,f[N],h,r,ans=0;
int find(int x){
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
void add(int x,int y){
	int r1=find(x),r2=find(y);
	f[r1]=r2;
}
int dis(int x,int y,int z){
	return x*x+y*y+z*z;
}
struct node{
	int x,y,z;
}mp[2000];
signed main () {
	int T;
	cin>>T;
	while(T--){
		cin>>n>>h>>r;
		memset(mp,0,sizeof(mp));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
			f[i]=i;
			cin>>mp[i].x>>mp[i].y>>mp[i].z;
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(find(i)==find(j))continue;
				if(dis(mp[i].x-mp[j].x,mp[i].y-mp[j].y,mp[i].z-mp[j].z)<=4*r*r){
					add(i,j);
				}
			}
		}
		bool s=0;
		for(int i=1;i<=n;i++){
			int minn=1e18,maxn=0;
			for(int j=1;j<=n;j++){
				if(f[j]==i){
					if(mp[j].z-r<minn){
						minn=mp[j].z-r;
					}
					if(mp[j].z+r>maxn){
						maxn=mp[j].z+r;
					}
				}
			}
			if(minn<=0&&maxn>=h){
				cout<<"Yes"<<endl;
				s=1;
				break;
			}
		}
		if(!s)cout<<"No"<<endl;
	}
	return 0;
}
2024/5/16 19:24
加载中...