题解 | #[NOIP2017]奶酪#

#include <bits/stdc++.h>
using namespace std;

struct Union
{
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;

    int find(int x)
    {
        if (!parent.count(x))
            parent[x] = x;
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int x, int y)
    {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx == rooty)
            return;

        if (rank[rootx] < rank[rooty])
            parent[rootx] = rooty;
        else if (rank[rootx] > rank[rooty])
            parent[rooty] = rootx;
        else
        {
            parent[rooty] = rootx;
            rank[rootx]++;
        }
    }
};

struct point
{
    int x, y, z;
    point(int x, int y, int z) : x(x), y(y), z(z) {}
};

bool judge(const point &a, const point &b, long long r)
{
    long long dx = 1LL * a.x - b.x;
    long long dy = 1LL * a.y - b.y;
    long long dz = 1LL * a.z - b.z;
    long long dist2 = dx * dx + dy * dy + dz * dz;
    return dist2 <= 4LL * r * r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int n, h, r;
        cin >> n >> h >> r;

        vector<point> v;
        v.reserve(n);
        for (int i = 0; i < n; i++)
        {
            int x, y, z;
            cin >> x >> y >> z;
            v.emplace_back(x, y, z);
        }

        Union u;
        // 初始化每个点的父节点为自己
        for (int i = 0; i < n; i++)
            u.find(i);

        // 合并相切或相交的洞
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (judge(v[i], v[j], r))
                {
                    u.unite(i, j);
                }
            }
        }

        // 记录每个连通分量的最小z-r和最大z+r
        unordered_map<int, int> min_z, max_z;
        for (int i = 0; i < n; i++)
        {
            int root = u.find(i);
            int cur_min = v[i].z - r;
            int cur_max = v[i].z + r;

            if (!min_z.count(root))
            {
                min_z[root] = cur_min;
                max_z[root] = cur_max;
            }
            else
            {
                min_z[root] = min(min_z[root], cur_min);
                max_z[root] = max(max_z[root], cur_max);
            }
        }

        bool flag = false;
        for (auto &[root, min_val] : min_z)
        {
            if (min_val <= 0 && max_z[root] >= h)
            {
                flag = true;
                break;
            }
        }

        cout << (flag ? "Yes" : "No") << '\n';
    }

    return 0;
}