求高手指点,才30分。样例三个YES
查看原帖
求高手指点,才30分。样例三个YES
534532
AnthonyEric楼主2022/6/6 22:12
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fa[114514];
ll find(ll x) 
{ 
	if(fa[x]==x) return x; 
	else  return fa[x] = find(fa[x]);    
}  
void merge(ll x,ll y) 
{ 
	ll rx=find(x); 
	ll ry=find(y); 
	if(rx!=ry) fa[rx]=ry; 
}  
ll ju(ll x1, ll x2, ll y1, ll y2, ll z1, ll z2){
	return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) + (z1 - z2)*(z1 - z2);
}
int main(){
	ll t;
	cin >> t;
	ll n, h, r;
	ll x, y ,z;
	ll ax[114514], ay[114514], az[114514];
	
	while(t--){
		ll flr[114514], cel[114514];
		int fln = 0, cein = 0;
		cin >> n >> h >> r;
		for(int i=1;i<=n;i++){
			flr[i] = 0;
			cel[i] = 0;
			fa[i] = i;
		}
		for(int i = 1; i <= n; i++){
			cin >> x >> y >> z;
			ax[i] = x, ay[i] = y, az[i] = z;
			if(z-r<= 0) flr[++fln] = i;
			if(z+r >= h) cel[++cein]= i;
			for(int j=1;j<=i;j++){
				if(ju(ax[i], x, ay[i], y, az[i], z) > 4*r*r) continue;
				if(ju(ax[i], x, ay[i], y, az[i], z) <= 4 *r*r) merge(i, j);
			}
		}
		int end1 = 0;
		for(int i=1;i<=fln;i++){
			for(int j=1;j<=cein;j++){
				ll aa = find(flr[i]), bb = find(cel[j]);
				if(aa == bb){end1 = 1; break;}
			}
			if(end1 == 1) break;
		}
		if(end1 == 1) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}
2022/6/6 22:12
加载中...