奶酪[并查集][NOIP2017]_奶酪并查集

又是一道并查集...

分析 

如果两个洞的dist小于2倍r,两个洞连通,合并为1个集合,一个集合里面的洞都可以两两到达

判断超过h的洞与在最底下的洞在不在连不连通即判断在不在一个集合

并查集判断集合----看祖先是否相同即可

代码

#include<bits/stdc++.h>
#define N 1005
#define LL long long 
using namespace std;
struct Node{int x,y,z;}a[N];
int T,n,h,r;
int fa[N],able1[N],able2[N],tot1,tot2;
int read(){
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}
	while(isdigit(ch))cnt=cnt*10+ch-'0',ch=getchar();
	return cnt*f;
}
LL dis(int i,int j){
	LL x=(LL)(a[i].x-a[j].x)*(a[i].x-a[j].x);
	LL y=(LL)(a[i].y-a[j].y)*(a[i].y-a[j].y);
	LL z=(LL)(a[i].z-a[j].z)*(a[i].z-a[j].z);
	return x+y+z;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	T=read();
	while(T--){
		n=read(),h=read(),r=read();
		memset(a,0,sizeof(a)),tot1=0,tot2=0;
		for(int i=1;i<=n;i++)fa[i]=i;
		for(int i=1;i<=n;i++)
			a[i].x=read(),a[i].y=read(),a[i].z=read();
		for(int i=1;i<=n;i++)//将可行的点存在数组里
			if(a[i].z-r<=0) able1[++tot1]=i;
		for(int i=1;i<=n;i++)
			if(a[i].z+r>=h) able2[++tot2]=i;
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
				if(dis(i,j)<=(LL)4*r*r){ //合并
					int x=find(i),y=find(j);
					if(x!=y) fa[x]=y;
				}
		for(int i=1;i<=tot1;i++)
			for(int j=1;j<=tot2;j++)
				if(find(able1[i])==find(able2[j])){cout<<"Yes"<<endl;goto die;}
		cout<<"No"<<endl;
		die:;
	}
	return 0;
}