求助40pts(悬赏关注,要包AC)
查看原帖
求助40pts(悬赏关注,要包AC)
529017
Smg18楼主2023/4/27 17:16
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fcli fclose(stdin)
#define fclo fclose(stdout)
#define D(i,j) dis(arr[i][1],arr[i][2],arr[i][3],arr[j][1],arr[j][2],arr[j][3])
const ll N = 1e5+10,NN=1e4+50;
ll n,m,k,T,r,h,len,maxn=INT_MIN,minn=INT_MAX,arr[N][10],f[N],v[N][2];
ll find(int x){
	if(f[x]==x)return x;
	else{
		return f[x]=find(f[x]);
	}
}
ll qf(int a,int b){
	int res=1;
	while(b){
		if(b&1)res*=a;
		a*=a;
		b>>=1;
	}
	return res;
}
bool dis(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2){
	ll xx=qf(abs(x1-x2),2);
	ll yy=qf(abs(y1-y2),2);
	ll zz=qf(abs(z1-z2),2);
	return (xx+yy+zz)<=4ll*r*r;
}
int main(){
//	freopen("party.in","r",stdin);
//	freopen("party.out","w",stdout);
	cin>>T;
	while(T--){
		int flag=0;
		cin>>n>>h>>r;
		for(int i = 1;i<=1000;i++){
			for(int j = 1 ;j<=1000;j++){
				v[i][j]=0;
			}
		}
		for(int i = 1;i<=n+2;i++){
			f[i]=i;
		}
		for(int i =1;i<=n;i++){
			cin>>arr[i][1]>>arr[i][2]>>arr[i][3];
		}
		for(int i =1;i<=n;i++){
			for(int j = i+1;j<=n;j++){
				if(dis(arr[i][1],arr[i][2],arr[i][3],arr[j][1],arr[j][2],arr[j][3])){
					
					f[i]=find(f[j]);
					
				}
			}
		}
		for(int i = 1;i<=n;i++){
			
		}
		for(int i =1;i<=n;i++){//爸爸 
			for(int j = 1;j<=n;j++){
				if(find(f[j])==i){
					if(arr[j][3]-r<=0)
						v[i][1]=1; 
					if(arr[j][3]+r>=h){
						v[i][2]=1;
					}
				}
			}
		}
		for(int i =1;i<=n;i++){
			if(v[i][1]==1&&v[i][2]==1){
				cout<<"Yes"<<endl;
				flag=1;
				break;
			}
		}
		if(!flag){
			cout<<"No"<<endl;
		}
	}
//	fcli;
//	fclo;
	return 0;

}
//3
//2 4 1
//0 0 1
//0 0 3
//2 5 1
//0 0 1
//0 0 4
//2 5 2
//0 0 2
//2 0 4
2023/4/27 17:16
加载中...