90分 求调
查看原帖
90分 求调
571132
Soft_cute楼主2023/9/8 19:12
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+10;
int t,n,h,r,f[N];
int ft[N],fb[N];
struct Node{
	int x,y,z;
}p[N];
bool check(Node a,Node b){
	long double dis=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
	if(dis>4.0*r*r) return false;
	else return true;
}
int find(int x){
	if(x==f[x]) return x;
	else f[x]=find(f[x]);
}
signed main(){
	freopen("P3958_7.in","r",stdin);
	freopen("P3958_8.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>n>>h>>r;
		int top=0,bot=0;
		for(int i=0;i<=n;i++) f[i]=i;
		for(int i=1;i<=n;i++){
			cin>>p[i].x>>p[i].y>>p[i].z;
		}
		for(int i=1;i<=n;i++){
			if(p[i].z+r>=h) top++,ft[top]=i;
			if(p[i].z-r<=0) bot++,fb[bot]=i;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=i;j++){
				if((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)+(p[i].z-p[j].z)*(p[i].z-p[j].z)>4.0*r*r)
				continue;
				if(check(p[i],p[j])==true){
					int fx=find(i);
					int fy=find(j);
				if(fx!=fy) f[fx]=fy;
				}
			}
		}
		bool k=false;
		for(int i=1;i<=top&&k==false;i++){
			for(int j=1;j<=bot&&k==false;j++){
				if(f[ft[i]]==f[fb[j]]){
					k=true;break;
				}
			}
		}
		if(k==true) cout<<"Yes"<<"\n";
		else cout<<"No"<<"\n";
	}
	fclose(stdin);
	fclose(stdout);
}
//第7个WA了
2023/9/8 19:12
加载中...