代码

#include<bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'
#define int long long

using i64 = long long;

template<typename T>
struct DSU
{
    std::vector<T> p, siz;
    DSU(int n): p(n + 1), siz(n + 1, 1) {std::iota(p.begin(), p.end(), 0);}
    int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
    bool same(int x, int y) {return find(x) == find(y);}
    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if(x == y)
            return false;
        siz[x] += siz[y];
        p[y] = x;
        return true;
    }
    int size(int x) {return siz[find(x)];}
};

void solve()
{
    int n, h, r;
    std::cin >> n >> h >> r;
    std::vector<i64> x(n + 1), y(n + 1), z(n + 1);
    for(int i = 1;i <= n;i++)
        std::cin >> x[i] >> y[i] >> z[i];
    
    auto dis = [&](int i, int j) -> double
    {
        double X = x[i] - x[j], Y = y[i] - y[j], Z = z[i] - z[j];
        return X * X + Y * Y + Z * Z;
    };
    auto checkup = [&](int pos) -> bool
    {
        return z[pos] + r >= h;
    };
    auto checkdown = [&](int pos) -> bool
    {
        return z[pos] - r <= 0;
    };

    DSU<i64> d(n);
    bool flag = 0;
    std::vector<int> pos, pos1;

    for(int i = 1;i <= n;i++)
    {
        if(checkdown(i))
            pos.emplace_back(i);
        if(checkup(i))
            pos1.emplace_back(i);
        for(int j = 1;j <= i;j++)
            if(dis(i, j) <= 4 * r * r)
                d.merge(i, j);
    }
    for(auto v: pos)
        for(auto u: pos1)
            if(d.same(v, u))
            {
                flag = 1;
                break;
            }
    if(flag)
        std::cout << "Yes\n";
    else
        std::cout << "No\n";
    return;
}

signed main()
{
    #ifdef ONLINE_JUDGE
    ioclear;
    #endif

    int t;
    std::cin >> t;
    while(t--)
        solve();
}

评测结果