代码

#include <iostream>
using namespace std;
typedef long long ll;

struct Sphere {
	ll x, y, z;
	Sphere(ll x=0, ll y=0, ll z=0): x(x), y(y), z(z) {}
};
#define MAXN 1050
Sphere sp[MAXN];
ll n, h, r;
int fa[MAXN];

ll sq(ll s) {
	return s * s;
}

ll distsq(Sphere s, Sphere p) {
	return sq(s.x - p.x) + sq(s.y - p.y) + sq(s.z - p.z);
}

bool intersect(Sphere s, Sphere p) {
	return distsq(s, p) <= 4 * r * r;
}

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

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

bool ufspr(int a, int b) {
	return ufsfind(a) == ufsfind(b);
}

void ufsmerge(int a, int b) {
	if (!ufspr(a, b))
		fa[ufsfind(a)] = fa[ufsfind(b)];
}

// Node 1 is bottom, Node n + 2 is top
void solveone() {
	cin >> n >> h >> r;
	ufsinit();
	for (int i = 2; i < n + 2; i++) {
		cin >> sp[i].x >> sp[i].y >> sp[i].z;
		if (sp[i].z <= r) {
			ufsmerge(1, i); 
//			cout << i << " bottom" << endl; 
		}
		if (sp[i].z + r >= h) { 
			ufsmerge(i, n + 2); 
//			cout << i << " top" << endl; 
		}
	}
	
	for (int i = 2; i < n + 1; i++)
	for (int j = i + 1; j < n + 2; j++) {
		if (intersect(sp[i], sp[j]))
			ufsmerge(i, j);
//		cout << i << " " << j << " " << intersect(sp[i], sp[j]) << endl;
	}
	
//	for (int i = 1; i <= n + 2; i++) cout << fa[i] << " "; cout << endl;
	if (ufsfind(1) == ufsfind(n + 2)) cout << "Yes" << endl;
	else cout << "No" << endl;
}

int main() {
	int z;
	cin >> z;
	while (z--) {
		solveone();
	}
	return 0;
}

评测结果