【并查集】【中间值范围】NOIP2017]奶酪

https://ac.nowcoder.com/acm/contest/22904/1027

开了ll还见祖宗
注意x^2 + y^{2算完之后先判断有没有超4r}2的范围，没有的话再计算z^2，算是对long long溢出的特判

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

class UnionFind {
public:
    UnionFind(ll n) : parent(n), rank(n, 1) {
        for (ll i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    ll find(ll x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unite(ll x, ll y) {
        ll rootX = find(x);
        ll rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    bool connected(ll x, ll y) {
        return find(x) == find(y);
    }

private:
    vector<ll> parent;
    vector<ll> rank;
};

// 计算两点之间的欧几里得距离平方
bool isConnected(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2, ll r) {
    ll dx = x1 - x2;
    ll dy = y1 - y2;
    ll dz = z1 - z2;
    if(dx * dx + dy * dy > 4 * r * r) {
        return false;
    }
    return dx * dx + dy * dy + dz * dz <= 4 * r * r;
}

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

        vector<tuple<ll, ll, ll>> holes(n);
        for (ll i = 0; i < n; ++i) {
            ll x, y, z;
            cin >> x >> y >> z;
            holes[i] = {x, y, z};
        }

        UnionFind uf(n);
        vector<int> bottom, top;

        for (int i = 0; i < n; ++i) {
            auto [x1, y1, z1] = holes[i];
            if (z1 <= r) {
                bottom.push_back(i);
            }
            if (z1 >= h - r) {
                top.push_back(i);
            }
            for (ll j = i + 1; j < n; ++j) {
                auto [x2, y2, z2] = holes[j];
                if (isConnected(x1, y1, z1, x2, y2, z2, r)) {
                    uf.unite(i, j);
                }
            }
        }

        bool canReach = false;
        for (ll b : bottom) {
            for (ll t : top) {
                if (uf.connected(b, t)) {
                    canReach = true;
                    break;
                }
            }
            if (canReach) break;
        }

        cout << (canReach ? "Yes" : "No") << endl;
    }

    return 0;
}