并查集只过5个点,求助!
查看原帖
并查集只过5个点,求助!
411009
我就是个逗比楼主2021/10/13 08:03
#include<bits/stdc++.h>
using namespace std;
int t;
int n,h,r,fa[1005],deap[1005],cnt;
struct node{
	int x,y,z;
}e[1010];

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

void unionn(int a,int b){
	if(e[a].z<=e[b].z)fa[find(a)]=find(b);
	else fa[find(b)]=find(a);
}

void st(){
	for(int i=1;i<=n;i++)fa[i]=i;
}

double dis(int a,int b){
	return sqrt(abs(e[a].x-e[b].x)*abs(e[a].x-e[b].x)+abs(e[a].y-e[b].y)*abs(e[a].y-e[b].y)+abs(e[a].z-e[b].z)*abs(e[a].z-e[b].z));
}

void work(){
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			if(dis(i,j)<=2*r)unionn(i,j);
//			cout<<fa[i]<<" "<<fa[j]<<endl; 
		}
	}
}

bool judge(){
	for(int i=1;i<=cnt;i++){
		if(e[find(deap[i])].z+r>=h)return 1;
	}
	return 0;
}

int main(){
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n>>h>>r;
		st();
		cnt=0;
		for(int j=1;j<=n;j++){
			cin>>e[j].x>>e[j].y>>e[j].z;
			if(e[j].z-r<0)deap[++cnt]=j;
		}
		work();
//		for(int i=1;i<=cnt;i++)cout<<find(deap[i])<<" ";
//		cout<<endl; 
		if(judge())cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
} 
2021/10/13 08:03
加载中...