思路与算法

球洞相交连边，连接上下表面两个虚点并查集判连通；用128位平方和比较4r²，不对题面漏根号的dist式再开方。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

相交或相切球洞可以互相到达，连接这些洞不会制造额外通路。下表面虚点连接所有可进入的洞，上表面虚点同理；两个虚点同代表元恰是存在合法洞链。

复杂度

每组O(n² α(n)+n)时间、O(n)空间；全部T组分别初始化。

易错点

三维差平方和可能超过64位；先提升到128位再乘。相切使用小于等于。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        long long h, r;
        cin >> n >> h >> r;
        vector<array<long long, 3>> a(n);
        for (auto &v : a)
            cin >> v[0] >> v[1] >> v[2];
        vector<int> p(n + 2);
        iota(p.begin(), p.end(), 0);
        function<int(int)> f = [&](int x) {
            return p[x] == x ? x : p[x] = f(p[x]);
        };
        auto un = [&](int a, int b) {
            p[f(a)] = f(b);
        };
        for (int i = 0; i < n; i++) {
            if (a[i][2] <= r)
                un(i, n);
            if (a[i][2] + r >= h)
                un(i, n + 1);
            for (int j = 0; j < i; j++) {
                __int128 d = 0;
                for (int k = 0; k < 3; k++) {
                    long long t = a[i][k] - a[j][k];
                    d += (__int128)t * t;
                }
                if (d <= (__int128)4 * r * r)
                    un(i, j);
            }
        }
        cout << (f(n) == f(n + 1) ? "Yes" : "No") << "\n";
    }
}