0分求助
查看原帖
0分求助
722836
lilincong楼主2022/11/26 15:10
#include <bits/stdc++.h>
using namespace std;

struct node
{
	long long x;
	long long y;	
	long long z; 
};

int t;
long long n,h,r;
node a[1010];
long long fa[1010];

long long getroot(long long x)
{
	if (fa[x]!=x)
	{
		fa[x]=getroot(fa[x]);
	}
	return fa[x];
}

void unon(long long x,long long y)
{
	long long fx = getroot(x);
	long long fy = getroot(y);
	if (fx!=fy)
	{
		fa[fx]=fy;
	}
}

bool check(long long x1,long long y1,long long z1,long long x2,long long y2,long long z2)
{
	return pow(x1-x2,2)+pow(y1-y2,2),pow(z1-z2,2)<=pow(2*r,2);
} 

int main()
{
	cin>>t;
	for (int k=1;k<=t;k++)
	{
		cin>>n>>h>>r;
		for (int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].y>>a[i].z;
		}
		for (int i=1;i<=n;i++)
		{
			fa[i]=i;
		}
		for (int i=1;i<=n;i++)
		{
			if (a[i].z-r<=0)
			{
				unon(0,i);
			}
			if (a[i].z+r>=h)
			{
				unon(i,n+1);
			 } 
			 for (int j=i+1;j<=n;j++)
			 {
			 	if (check(a[i].x,a[i].y,a[i].z,a[j].x,a[j].y,a[j].z))
			 	{
			 		unon(i,j);
				}
			 }
		}
		if (getroot(0)==getroot(n+1))
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
	return 0;
}
2022/11/26 15:10
加载中...