题解：P3958 [NOIP2017 提高组] 奶酪

pipilong2024 · 2025-01-05 18:54:29 · 题解

题解区的大部分竟都被 dfs 和 bfs 占领了，个别写并查集又被卡了。这忍得了 （我又不是忍者）！

针对于每一个空洞我们定义：
最大高度 = 球心高度 + 该球半径，表示在这个球内所能到达的最高的高度；
最小高度 = 球心高度 - 该球半径，表示在这个球内所能到达的最矮的高度。
当两个空洞 P_1(x_1,y_1,z_1)、P2(x_2,y_2,z_2) 相切或是相交时，一定满足（如题所述）：

为避免精度问题，两边平方（去根号）得

此时便可更新 最大高度 和 最小高度，使用并查集合并，具体操作见代码。
最后只需查看是否存在一个空洞使得其 最大高度 \ge h，最小高度 \le 0 即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long//十年OI一场空，不开____一场空
int n, h, r, t;//如题目
struct Node {
    int x, y, z;
} a[1001];//空洞节点
int fa[1002], min_h[1002], max_h[1002];
//fa是父亲编号，min_h是最小高度，max_h是最大高度
int dist(int x1, int x2, int y1, int y2, int z1, int z2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2);
}
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}//并查集函数
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> h >> r;
        for (int i = 1; i <= n; i++) {
            cin >> a[i].x >> a[i].y >> a[i].z;
          //初始化 fa，min_h 和 max_h
            fa[i] = i;
            min_h[i] = a[i].z - r;
            max_h[i] = a[i].z + r;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (4 * r * r >= dist(a[i].x, a[j].x, a[i].y, a[j].y, a[i].z, a[j].z)) {
                    int ri = find(i), rj = find(j);
                    fa[rj] = ri;//合并
          //更新 min_h 和 max_h
                    min_h[ri] = min(min_h[ri], min_h[rj]);
                    max_h[ri] = max(max_h[ri], max_h[rj]);
                }
            }
        }
        bool flag = 0;
        for (int i = 1; i <= n; i++) {
            if (fa[i] != i) continue;
            if (min_h[i] <= 0 && max_h[i] >= h) {//见上
                flag = 1;
                break;
            }
        }
        if (flag) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

小注：80 分的同学考虑一下精度问题和范围问题，别问我怎么知道——\color{red}{血}的教训。