代码

// This code is AI-generated. (AI 生成的代码)
// NOIP2017 奶酪: DFS over the sphere-intersection graph starting from spheres
// touching the bottom; succeed if a sphere touching the top is reached.
// Squared distances use 64-bit with term-by-term bounding (no __int128).
#include <stdio.h>
typedef long long ll;
static ll X[1005], Y[1005], Z[1005];
static char vis[1005];
static int n;
static ll h, r, r2;
static inline int hit(int i, int j) {
    ll dx = X[i] - X[j], dy = Y[i] - Y[j], dz = Z[i] - Z[j];
    ll ax = dx < 0 ? -dx : dx, ay = dy < 0 ? -dy : dy, az = dz < 0 ? -dz : dz;
    ll q = ax * ax;
    if (q > r2) return 0;
    q += ay * ay;
    if (q > r2) return 0;
    return az * az <= r2 - q;
}
static int dfs(int u) {
    vis[u] = 1;
    if (Z[u] + r >= h) return 1;
    for (int j = 0; j < n; j++)
        if (!vis[j] && hit(u, j) && dfs(j)) return 1;
    return 0;
}
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;
    int T;
    while (*gp < '0') gp++;
    T = 0; while (*gp >= '0' && *gp <= '9') T = T * 10 + (*gp++ - '0');
    while (T--) {
        while (*gp < '0') gp++;
        n = 0; while (*gp >= '0' && *gp <= '9') n = n * 10 + (*gp++ - '0');
        while (*gp < '0') gp++;
        h = 0; while (*gp >= '0' && *gp <= '9') h = h * 10 + (*gp++ - '0');
        while (*gp < '0') gp++;
        r = 0; while (*gp >= '0' && *gp <= '9') r = r * 10 + (*gp++ - '0');
        r2 = 4 * r * r;
        for (int i = 0; i < n; i++) {
            vis[i] = 0;
            while (*gp < '0' && *gp != '-') gp++;
            int neg = (*gp == '-'); if (neg) gp++;
            ll v = 0; while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0');
            X[i] = neg ? -v : v;
            while (*gp < '0' && *gp != '-') gp++;
            neg = (*gp == '-'); if (neg) gp++;
            v = 0; while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0');
            Y[i] = neg ? -v : v;
            while (*gp < '0' && *gp != '-') gp++;
            neg = (*gp == '-'); if (neg) gp++;
            v = 0; while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0');
            Z[i] = neg ? -v : v;
        }
        int ok = 0;
        for (int i = 0; i < n && !ok; i++)
            if (!vis[i] && Z[i] <= r && dfs(i)) ok = 1;
        if (ok) { 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;
}

评测结果