玄关求条
查看原帖
玄关求条
1108111
XYY62012楼主2024/12/15 11:15
#include<bits/stdc++.h>
using namespace std;
int f[1001];//并查集 
int n,h; 
long long r;
int f1[100001],f2[100001];//分别记录上下面相交的洞序号
long long x[100001],y[100001],z[100001];

int find(int x){//查找
    if (x!=f[x]) f[x]=find(f[x]);
    return f[x];
}
long long dis(long long x,long long y,long long z,long long x1,long long y1,long long z1){
    int sum=(x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1);
    return sum;
}//两点距离公式,注意这里算的是距离平方
int main(){
    int t;
    cin>>t;
    for (int i=1;i<=t;i++){
        cin>>n>>h>>r;
        int tot1=0;//记录与顶面相交的洞有几个
        int tot2=0;//记录与底面相交的洞有几个
        for (int j=1;j<=n;j++){
          f[j]=j;  //并查集初始化
         }
        for (int j=1;j<=n;j++){
            cin>>x[j]>>y[j]>>z[j];
            if (z[j]+r>=h){//判断这个点是否与顶面相交
                tot1++;
                f1[tot1]=j;
            }
            if (z[j]-r<=0){//判断这个点是否与底面相交
                tot2++;
                f2[tot2]=j;
            }
            for (int k=1;k<=j;k++){//枚举之前的洞是否与这个洞相交,如果相交则合并集合
            	//if ((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])>4*r*r) continue;
                if (dis(x[j],y[j],z[j],x[k],y[k],z[k])<=4*r*r){
                    if (find(j)!=find(k)){
                    	f[find(j)]=find(k);
					} 
                }
            }
        }
        int num=0;
        for (int j=1;j<=tot1;j++){
            for (int k=1;k<=tot2;k++){
                if (find(f1[j])==find(f2[k])){
                    num=1; 
                    break;
                }
            }
            if (num==1) break;
        }
        if(num==1){
        	cout<<"Yes"<<endl;
		} 
        else{
        	cout<<"No"<<endl;
		} 
    }
    return 0;
}
2024/12/15 11:15
加载中...