并查集50分求调,玄关
查看原帖
并查集50分求调,玄关
983684
yangduan_楼主2024/7/15 08:18
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll t,n,h,r,fa[10010],shang[10010],xia[10010];
struct node{
	ll c,k,g,id;
}a[10010];
double dis(int x,int y){
	ll xc=a[x].c,xk=a[x].k,xg=a[x].g;
	ll yc=a[y].c,yk=a[y].k,yg=a[y].g;
	ll cc=xc-yc,kc=xk-yk,gc=xg-yg;
	return (double)sqrt((double)cc*cc+(double)kc*kc+(double)gc*gc);
}
ll find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void merge(int x,int y){//合并 
	if(a[x].g>=a[y].g){
		fa[find(y)]=find(x);
	}else{
		fa[find(x)]=find(y);
	}
}
int main(){
	int i,j;
	cin>>t;
	while(t--){
		memset(shang,0,sizeof(shang));
		memset(xia,0,sizeof(xia));
		memset(fa,0,sizeof(fa));
		memset(a,0,sizeof(a));
		cin>>n>>h>>r;
		ll d=2*r;
		for(i=1;i<=n;i++){
			cin>>a[i].c>>a[i].k>>a[i].g;
			fa[i]=i;
		}
		for(i=1;i<n;i++){
			for(j=i+1;j<=n;j++){
				if(dis(i,j)<=d){
					merge(i,j);
				}
			}
		}
		for(i=1;i<=n;i++){
			if(a[i].g-r<=0){
				xia[i]=1;
			}
			if(a[i].g+r>=h){
				shang[i]=1;
			}
		}
		for(i=1;i<=n;i++){
			if(xia[i]){
				if(shang[find(i)]){
					cout<<"Yes"<<endl;
					goto yd;
				}
			}
		}
		cout<<"No"<<endl;
		yd:;
	}
	return 0;
}
2024/7/15 08:18
加载中...