并查集80 9 10WA
查看原帖
并查集80 9 10WA
525691
wfgygfsrssh080272楼主2023/11/25 09:14
#include<bits/stdc++.h>
using namespace std;

int T;
long long n,h,r;
long long x[1005],y[1005],z[1005];
int fa[1005];

int findf(long long xx){
	if(fa[xx]==xx) return xx;
	return fa[xx]=findf(fa[xx]);
}

void Union(long long x,long long y){
	long long fax=findf(x);
	long long fay=findf(y);
	fa[fax]=y;
}

int dist(long long x1,long long x2,long long y1,long long y2,long long z1,long long z2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i]>>z[i];
		}
		for(int i=1;i<=n+2;i++){
			fa[i]=i;
		}
		
		for(int i=1;i<=n;i++){
			if(z[i]+r>=h) Union(i,n+1);
			if(z[i]-r<=0) Union(i,n+2);
		}
		
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(findf(i)==findf(j)) continue;
				if(dist(x[i],x[j],y[i],y[j],z[i],z[j])<=4*r*r){
					Union(i,j);
                }
			}
		}
		if(findf(n+2)==findf(n+1)){
			cout<<"Yes"<<endl;
		}
		else cout<<"No"<<endl;
	}
	return 0;
}

2023/11/25 09:14
加载中...