代码

#include<cstdio>
#include<cstring>
typedef long long ll;
const int maxn = 1010;
inline void write(ll x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10);
    putchar(x % 10 + 48);
}
inline ll read() {
    ll k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        k = (k << 1) + (k << 3) + c - 48;
        c = getchar();
    }
    return k * f;
}
struct Set_Union {
    static const int maxn = 1010;
    int f[maxn], size[maxn];
    inline void init(int n) {
        for (int i = 1; i <= n; ++i)f[i] = i, size[i] = 1;
    }
    int getf(int x) {
        return f[x] == x ? x : f[x] = getf(f[x]);
    }
    bool check(int x, int y) {
        int a = getf(x);
        int b = getf(y);
        if (a != b) return false;
        else return true;
    }
    void merge(int x, int y) {
        int a = getf(x);
        int b = getf(y);
        if (a == b) return;
        if(size[a] > size[b])
            f[b] = a, size[a] += size[b], size[b] = 0;
        else
            f[a] = b, size[b] += size[a], size[a] = 0;
    }
} Union;
int top[maxn], top_size;
int bot[maxn], bot_size;
ll T;
ll n, h, r;
ll d2;
ll x[maxn], y[maxn], z[maxn];
ll dis2(int i, int j) {
    return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j]);
}
bool isIntersection(int i, int j) {
    return dis2(i, j) <= d2;
}
inline void init() {
    Union.init(n);
    top_size = bot_size = 0;
}
bool flag;
int main() {
    T = read();
    while(T--) {
        flag = false;
        n = read(), h = read(), r = read();
        d2 = (r * r) << 2;
        init();
        for(int i = 1; i <= n; ++i) {
            x[i] = read(), y[i] = read(), z[i] = read();
            if(z[i] + r >= h) top[++top_size] = i;
            if(z[i] - r <= 0) bot[++bot_size] = i;
            for(int j = 1; j < i; ++j) if(isIntersection(i, j)) Union.merge(i, j);
        }
        for(int i = 1; i <= top_size && !flag; ++i)
        for(int j = 1; j <= bot_size && !flag; ++j)
        if(Union.check(top[i], bot[j])) flag = true;
        puts(flag ? "Yes" : "No");
    }
}

评测结果