【第11题】历经7小时磨难，死磕到底，有结果

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

struct edge {
    long long k, x, y, z;
};

struct UF {
    vector<edge> fa;
    vector<int> c;
    vector<int> s;

    UF(int n) :
            fa(n + 1), c(n + 1), s(n + 1) {}

    bool dis(edge a, edge b, long long r) {
        if (pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + pow(a.z - b.z, 2) <= 4 * r * r) {
            return true;
        } else {
            return false;
        }
    }

    long long Find(long long a) {
        if (a != fa[a].k) { //如果a的父节点不是本身，就往前找到其祖宗节点
            fa[a].k = Find(fa[a].k); //往回返的时候把路上遍历过的所有节点更新为祖宗节点
        }
        return fa[a].k;
    }

    void Union(edge x, edge y, long long r) {
        long long a = Find(x.k);
        long long b = Find(y.k); //找到两个数的祖宗节点
        if (a != b && dis(x, y, r)) {
            fa[b].k = a; //合并时只改其祖宗节点
        }
    }

    bool tf(int b, int d) {
        for (int i = 1; i <= b; ++i) {
            for (int j = 1; j <= d; ++j) {
                if (Find(c[i]) == Find(s[j])) {
                    return true;
                }
            }
        }
        return false;
    }
};

void best_coder() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        int n, h;
        long long r;
        cin >> n >> h >> r;
        UF uf(n);
        int cnt_1 = 0;
        int cnt_2 = 0;
        for (int j = 1; j <= n; ++j) {
            uf.fa[j].k = j;
            cin >> uf.fa[j].x >> uf.fa[j].y >> uf.fa[j].z;
            if (uf.fa[j].z + r >= h) {
                cnt_1++;
                uf.c[cnt_1] = j;
            }
            if (uf.fa[j].z - r <= 0) {
                cnt_2++;
                uf.s[cnt_2] = j;
            }
            for (int k = 1; k <= j; ++k) {
                if (!uf.dis(uf.fa[j], uf.fa[k], r)) {
                    continue;
                }
                if (uf.dis(uf.fa[j], uf.fa[k], r)) {
                    uf.Union(uf.fa[j], uf.fa[k], r);
                }
            }
        }
        if (uf.tf(cnt_1, cnt_2)) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }
    }

}


void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}