80pts求助
查看原帖
80pts求助
400468
Aakkosetsumussa楼主2023/6/28 09:50
#include<bits/stdc++.h>
using namespace std;
long long n,h,r,f[500005],a[100005],H[500005],sum=0,k;
double x[100005],y[100005],z[100005];
int getf(int v) {
	if(f[v]==v) return v;
	return f[v]=getf(f[v]);
}
void merge(int v,int u) {
	int t1=getf(v),t2=getf(u);
	if(H[t1]==H[t2]) {
		H[t1]++;
		f[t2]=t1;
	} else if(H[t1]<H[t2]) {
		f[t1]=t2;
	} else f[t2]=t1;
}
int T;
inline double dis(double xa,double ya,double za,double xe,double ye,double ze) {
	return (pow(xa-xe,2)+pow(ya-ye,2)+pow(za-ze,2));
}
int main() {
	cin>>T;
	while(T--) {
		scanf("%d %d %d",&n,&h,&r);
		for(int i=0; i<=n+1; i++) f[i]=i,x[i]=y[i]=z[i]=0;
		for(int i=1; i<=n; i++)
			cin>>x[i]>>y[i]>>z[i];
		for(int i=1; i<=n; i++)
			for(int j=1; j<=i; j++) {
				if(i!=j) {
					int d=dis(x[i],y[i],z[i],x[j],y[j],z[j]);
					if(d<=4*r*r) merge(i,j);
				}
			}
		for(int i=1; i<=n; i++) {
			if(z[i]+r>=h) merge(i,n+1);
			if(z[i]-r<=0) merge(i,0);
		}
		if(getf(0)==getf(n+1)) cout<<"Yes";
		else cout<<"No";
		cout<<endl;
	}

	return 0;
}/*

*/
2023/6/28 09:50
加载中...