并查集wa #8#10,悬关求调
查看原帖
并查集wa #8#10,悬关求调
1087173
guer_loser_lcz楼主2024/1/23 10:03
#include<bits/stdc++.h>
using namespace std;
long long n,h,r,t;
long long f[1010],c[1010],k[1010],g[1010];
bool sq[1010],xq[1010];
long long find(long long x){
	if(x==f[x])return x;
	return f[x]=find(f[x]);
}
void cbj(long long x,long long y){
	if(find(x)!=find(y))f[find(y)]=find(x);
}
bool cx(long long x,long long y){
	if(find(x)==find(y))return 1;
	return 0;
}
long long nf(long long a,long long b){
	return (a-b)*(a-b);
}
bool check(long long x1,long long x2,long long y1,long long y2,long long z1,long long z2){
	long long kkk=sqrt(nf(x1,x2)+nf(y1,y2)+nf(z1,z2));
	if(2*r>=kkk)return 1;
	return 0;
}
bool flag;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>h>>r;
		flag=0;
		for(long long i=1;i<=n;i++){
		    xq[i]=sq[i]=0;
		    f[i]=i;
		}
		for(long long i=1;i<=n;i++){
			cin>>c[i]>>k[i]>>g[i];
			if(h-g[i]<=r)sq[i]=1;
			if(g[i]<=r)xq[i]=1;
			for(long long j=1;j<i;j++){
				if(check(c[i],c[j],k[i],k[j],g[i],g[j])){
					cbj(i,j);
				}
			}
		}
		for(long long i=1;i<=n;i++){
			if(xq[i]){
				for(long long j=1;j<=n;j++){
					if(sq[j]){
						if(cx(i,j)){
							flag=1;
							break;
						}
						if(flag)break;
					}
				}
			}
			if(flag)break;
		}
		if(flag)cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}
2024/1/23 10:03
加载中...