如果你算法对,注意distant精度问题&开long long
查看原帖
如果你算法对,注意distant精度问题&开long long
1062212
xuzb楼主2025/7/3 10:44
//2025年7月3日09:25:49
//加 long long 80pts 
//加 double 100pts 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e3+5;
int T;
int n,h,r;
struct ball{
	int x,y,z;
}a[maxn];
int fa[maxn];
bool fit(int p,int q){
	int xdist,ydist,zdist;
	xdist=abs(a[p].x-a[q].x);
	ydist=abs(a[p].y-a[q].y);
	zdist=abs(a[p].z-a[q].z);
	double dist=sqrt(xdist*xdist+ydist*ydist+zdist*zdist);//开double 注意精度 
	if(dist<=r*2)
		return true;
	return false;
}
int find(int p){
	while(p!=fa[p])
		p=fa[p];
	return p;
}
void merge(int p,int q){
	p=find(p),q=find(q);
	if(p==q)return ;
	fa[p]=q;
	return ;
}
signed main(){
	cin>>T;
	while(T--){
		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++){
			for(int j=1;j<i;j++){
				if(fit(i,j))
					merge(i,j);
			}
		}
		//判断联通
		int s1[maxn],s2[maxn];
		int p1=1,p2=1;
		for(int i=1;i<=n;i++){
			if(a[i].z<=r){
				s1[p1++]=find(i);
			}
			if(a[i].z>=h-r){
				s2[p2++]=find(i);
			}
		}
		bool f=false;
		for(int i=1;i<p1;i++)
			for(int j=1;j<p2;j++){
				if(s1[i]==s2[j]){
					f=true;
				}
			}
		if(f)cout<<"Yes";
		else cout<<"No"; 
		cout<<endl;
	}
	return 0;
}
2025/7/3 10:44
加载中...