代码

// This code is AI-generated. (AI 生成的代码)
#include <stdio.h>
// NOIP2017 奶酪: two spheres are connected iff centre distance <= r1+r2; union
// bottom (z<=r) and top (z+r>=h) into a DSU, answer Yes iff they connect.
// Coordinates reach 1e9 so squared distances need __int128.
typedef long long ll;
typedef __int128 lll;
static int fa[1005];
static inline int find(int x) {
    while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; }
    return x;
}
static inline void uni(int a, int b) { a = find(a); b = find(b); if (a != b) fa[a] = b; }
static ll X[1005], Y[1005], Z[1005];
static char buf[1 << 20], ob[1 << 12];
static char *gp;

int main() {
    int len = (int)fread(buf, 1, sizeof(buf) - 1, stdin);
    buf[len] = 0; gp = buf;
    char *op = ob;
#define RD(dst) do { while (*gp < '0' && *gp != '-') gp++; int neg = (*gp == '-'); if (neg) gp++; ll v = 0; while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0'); dst = neg ? -v : v; } while (0)
    ll T; RD(T);
    while (T--) {
        ll n, h, r; RD(n); RD(h); RD(r);
        for (int i = 0; i < n; i++) { RD(X[i]); RD(Y[i]); RD(Z[i]); fa[i] = i; }
        fa[n] = n; fa[n + 1] = n + 1;
        ll r2 = 4 * r * r;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                ll dx = X[i] - X[j], dy = Y[i] - Y[j], dz = Z[i] - Z[j];
                lll d2 = (lll)dx * dx + (lll)dy * dy + (lll)dz * dz;
                if (d2 <= (lll)r2) uni(i, j);
            }
        for (int i = 0; i < n; i++) {
            if (Z[i] <= r) uni(i, (int)n);
            if (Z[i] + r >= h) uni(i, (int)n + 1);
        }
        if (find((int)n) == find((int)n + 1)) { op[0]='Y'; op[1]='e'; op[2]='s'; op[3]='\n'; op += 4; }
        else { op[0]='N'; op[1]='o'; op[2]='\n'; op += 3; }
    }
    fwrite(ob, 1, op - ob, stdout);
    return 0;
}

评测结果