AcWing 528. 奶酪
原题链接
简单
作者:
逸误
,
2024-03-21 00:13:02
,
所有人可见
,
阅读 4
//并查集两步:判断是否联通、合并集合
//这里只需要把判断是否联通分成上下界和气泡是否联通和气泡之间是否联通两个问题来判断即可!
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
typedef long long LL;
int n,h,r;
struct Sphere
{
int x,y,z;
}q[N];
int p[N];//并查集数组!
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];//自己写的时候错了!!不能return x,一定要返回公共的父结点!!!
}
int main()
{
int t;
cin>>t;
while(t--)
{
scanf("%d%d%d",&n,&h,&r);
for(int i=0;i<=n+1;i++) p[i]=i;//初始化并查集数组
for(int i=1;i<=n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
q[i]={x,y,z};
if(abs(z)<=r)
p[find(i)]=find(0);//0不是结点,是预留给最下层表面的
if(abs(z-h)<=r)
p[find(i)]=find(n+1);//n+1不是结点,是预留给最上层表面的
}//巧妙!先处理出和上下表面相切的点,将上下表面和它放入一个并查集中!!
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)//遍历所有存在的点,看是否相连
{
LL dx=q[i].x-q[j].x;
LL dy=q[i].y-q[j].y;
LL dz=q[i].z-q[j].z;
if(dx*dx+dy*dy+dz*dz<=4*(LL)r*r)
p[find(i)]=find(j);//i和j连通,在一个并查集中
//顺序不重要,反正并查集连通即可
}
if(find(0)==find(n+1))
puts("Yes");
else
puts("No");
}
return 0;
}