并查集40分求助,只ac了前四个点
查看原帖
并查集40分求助,只ac了前四个点
908988
Zailu楼主2023/7/26 14:19
#include<bits/stdc++.h>
#define eps 1e-7
typedef long long ll;
using namespace std;

int n,h,r;

struct roun
{
	int x,y,z;
}a[1005];//存储孔

int fa[1005];
vector<int> ups;//存储联通上表面的孔
vector<int> dos;//存储联通下表面的孔

int check(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2)
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2)<=4LL*r*r;
}

int find(int x)
{
	if(fa[x]!=x)
		fa[x]=find(fa[x]);
	return fa[x];
}

int main()
{
	int T;
	cin>>T;
	for(int TT=0;TT<T;TT++)
	{
		cin>>n>>h>>r;
		ups.clear();
		dos.clear();
		for(int i=0;i<n;i++)
		{
			cin>>a[i].x>>a[i].y>>a[i].z;
			fa[i]=i;
			if(a[i].z<=r)
				dos.push_back(i);
			if(h-a[i].z<=r)
				ups.push_back(i);
		}
		if(dos.empty()||ups.empty())
		{
			cout<<"No"<<endl;
			continue;
		}
		
		for(int i=0;i<n;i++)
		{
			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))
				{
					int fi=find(i);
					int fj=find(j);
					if(fi!=fj)
						fa[j]=fa[i];
				}
			}
		}
		
		int sgn=0;
		for(int i=0;i<dos.size();i++)
		{
			for(int j=0;j<ups.size();j++)
			{
				if(find(dos[i])==find(ups[j]))
				{
					sgn=1;
					break;
				}
			}
			if(sgn)
				break;
		}
		cout<<(sgn?"Yes":"No")<<endl;
	}
	return 0;
}

2023/7/26 14:19
加载中...