比比不压行并查集作法谁更短
查看原帖
比比不压行并查集作法谁更短
606278
封禁用户楼主2024/2/26 22:27
// 1<=n<=1e3 1<=h,r<=1e9 t<=20
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e3+5;

int n,h,r,x[MAXN],y[MAXN],z[MAXN],fa[MAXN];

int fath(int id){return fa[id]=(fa[id]==id?id:fath(fa[id]));}
void mer(int x,int y){fa[fath(x)]=fath(y);}
double dist(int x1,int y1,int z1,int x2,int y2,int z2){return sqrt(pow(x1-x2,2)+pow(y1-y2,2)+pow(z1-z2,2));}

signed main(){
	int t;
	scanf("%d",&t);
	while (t--){
		scanf("%d %d %d",&n,&h,&r);
		for (int i=0;i<=n+1;i++) fa[i]=i;
		for (int i=1;i<=n;i++)
			scanf("%d %d %d",&x[i],&y[i],&z[i]);

		for (int i=1;i<=n;i++) if (z[i]<=r) mer(0,i);
		for (int i=1;i<=n;i++) if (h-z[i]<=r) mer(n+1,i);
		for (int i=1;i<=n;i++)
			for (int j=i+1;j<=n;j++)
				if (dist(x[i],y[i],z[i],x[j],y[j],z[j])<=2*r)
					mer(i,j);

		if (fath(0)==fath(n+1)) printf("Yes\n");
		else printf("No\n");
	}

	return 0;
}
2024/2/26 22:27
加载中...