并查集求条
查看原帖
并查集求条
566176
__ZTY__楼主2023/10/25 12:57
#include<bits/stdc++.h>
using namespace std;
struct idx{
	int x,y,z;
}a[1010];
int t,n,h,r,f[1010];
int getfa(int a){
	if(f[a]!=a)return f[a]=getfa(f[a]);
	return a;
}
void merge(int a,int b){
	if(getfa(a)!=getfa(b))f[a]=getfa(b);
}
int square(int x){
	return x*x;
}
int dis(int l,int r){
	return sqrt(square(a[l].x-a[r].x)+square(a[l].y-a[r].y)+square(a[l].z-a[r].z));
}
int main(){
	for(cin>>t;t--;){
		cin>>n>>h>>r;
		for(int i=0;i<=n+1;i++)f[i]=i;
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			cin>>a[i].x>>a[i].y>>a[i].z;
			if(a[i].z<=r)merge(i,0);
			if(a[i].z+r>=h)merge(i,n+1);
			for(int j=1;j<=i-1;j++){
				if(dis(i,j)<=r*2){
					merge(i,j);
				}
			}
		}
		for(int i=0;i<=n+1;i++){
			getfa(i);
		}
		if(f[0]==f[n+1])cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

2023/10/25 12:57
加载中...