40pts求助
查看原帖
40pts求助
800322
Zouzhuoxuan楼主2023/4/25 17:17
#include<bits/stdc++.h>
#define int long long
#define ceil cei
#define floor flo
using namespace std;
const int N=1005;
struct ball
{
	int x,y,z;
}a[N];
int root[N],ceil[N],floor[N];
int POW(int x){return x*x;}
int dis(ball _1,ball _2){return POW(_1.x-_2.x)+POW(_1.y-_2.y)+POW(_1.z-_2.z);}
int rt(int s){if(root[s]!=s) return root[s]=rt(root[s]);return s;}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int i,j,n,h,r,uf=0,uc=0;bool s=false;
		cin>>n>>h>>r;
		for(i=1;i<=n;i++) root[i]=i;
		for(i=1;i<=n;i++) 
		{
			cin>>a[i].x>>a[i].y>>a[i].z;
			if(a[i].z<=r) floor[++uf]=i;
			if(a[i].z+r>=h) ceil[++uc]=i;
			for(j=1;j<i;j++) 
			{
				if(POW(a[i].x-a[j].x)+POW(a[i].y-a[j].y)>=POW(2ll*r)) continue;
				if(dis(a[i],a[j])<=POW(2ll*r)&&rt(i)!=rt(j)) root[i]=j;
			}
		}
		for(i=1;i<=uf;i++)
		{
			for(j=1;j<=uc;j++) if(rt(ceil[i])==rt(floor[j])){s=true;break;}
			if(s) break;
		}
		if(s) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}
2023/4/25 17:17
加载中...