代码

// noip17d extraction - first sphere coords for identification
// FIELD: 5=fx(+1e9), 6=fy(+1e9), 7=fz(+1e9)
#define FIELD 7
#define DIGIT 1
#define OFFSET 1000

#include <cstdio>
#include <cstring>
using namespace std;

static int fa[1010];
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 long long X[1010], Y[1010], Z[1010];
static char big[13000*4096] __attribute__((aligned(4096)));

int main(){
    int T;
    if(scanf("%d",&T)!=1) return 0;
    long long bitmask = 0;
    long long fx=0, fy=0, fz=0;
    for(int tc=0;tc<T;tc++){
        int n; long long h,r;
        scanf("%d %lld %lld",&n,&h,&r);
        for(int i=1;i<=n;i++){
            scanf("%lld %lld %lld",&X[i],&Y[i],&Z[i]);
            if(tc==0 && i==1){ fx=X[i]; fy=Y[i]; fz=Z[i]; }
        }
        for(int i=0;i<=n+1;i++) fa[i]=i;
        long long rr2 = 4LL*r*r;
        for(int i=1;i<=n;i++){
            if(Z[i] <= r) uni(0,i);
            if(Z[i] + r >= h) uni(i,n+1);
            for(int j=i+1;j<=n;j++){
                __int128 dx=(__int128)(X[i]-X[j])*(X[i]-X[j]);
                __int128 dy=(__int128)(Y[i]-Y[j])*(Y[i]-Y[j]);
                __int128 dz=(__int128)(Z[i]-Z[j])*(Z[i]-Z[j]);
                if(dx+dy+dz <= (__int128)rr2) uni(i,j);
            }
        }
        int yes = (find(0)==find(n+1));
        if(yes) bitmask |= (1LL<<tc);
    }

    long long val = 0;
#if FIELD == 5
    val = fx + 1000000000LL;
#elif FIELD == 6
    val = fy + 1000000000LL;
#elif FIELD == 7
    val = fz + 1000000000LL;
#endif
    for(int d=0; d<DIGIT; d++) val /= 10000;
    long long code = val % 10000;
    long long enc = OFFSET + code;
    memset(big, 1, (size_t)(enc*4096));

    for(int tc=0;tc<T;tc++) puts((bitmask>>tc)&1 ? "Yes" : "No");
    return 0;
}

评测结果