https://www.luogu.com.cn/problem/P3958
并查集
预处理任意两点之间能否连边,以及任意点和上表面以及下表面能否连边。
存所有可以连的边
最后遍历所有边,并查集连边
然后看上表面和下表面是否连上就行
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, h, r, fa[1010];
struct Node {
double x, y, z;
} node[1010];
struct Edge {
int u, v;
} edge[N];
double dis(Node a, Node b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) +
(a.z - b.z) * (a.z - b.z));
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool solve() {
cin >> n >> h >> r;
for (int i = 1; i <= n; i++) {
cin >> node[i].x >> node[i].y >> node[i].z;
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
// 如果node[i]和node[j]之间的距离小于等于2 * r 说明两个空洞相切或相交
double d = dis(node[i], node[j]);
if (d <= 2 * r) {
edge[++cnt] = {i, j};
}
}
}
// 看各个点能否和上边界和下边界连起来
for (int i = 1; i <= n; i++) {
if (node[i].z <= r) edge[++cnt] = {i, 0};
if (h - node[i].z <= r) edge[++cnt] = {i, n + 1};
}
for (int i = 0; i <= n + 1; i++)
fa[i] = i;
for (int i = 1; i <= cnt; i++) {
int u = edge[i].u, v = edge[i].v;
int ru = find(u), rv = find(v);
if (ru != rv)
fa[ru] = rv;
if (find(0) == find(n + 1))
return true;
}
return false;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
cout << (solve() ? "Yes" : "No") << '\n';
}
return 0;
}