P3958 [NOIP2017 提高组] 奶酪 - 洛谷题解

#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
struct p{
    int x, y, z;
}point[1005];
double dist(p p1, p p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2) + pow(p1.z - p2.z, 2));
}
int f[1005];    // 底层为0，顶层为n+1 
int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
} // 路径压缩 
void merge(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if(faA != faB)
        f[faA] = faB;
} // 合并 
int t;
int n, h, r;
int main() {
    scanf("%d", &t);
    vector<bool> res;
    while(t--){
        scanf("%d %d %d", &n, &h, &r);
        // 初始化并查集
        for(int i = 0; i <= n + 1; i++) {
            f[i] = i;
        } 
         for(int i = 1; i <= n; i++) {
            int x, y, z;scanf("%d %d %d", &x, &y, &z);
            point[i] = (p){x, y, z};
            if(z - r <= 0) merge(i, 0); // 合并到底层 
            if(z + r >= h) merge(i, n + 1); // 合并到顶层 
            // 洞间合并
            for(int j = 1; j < i; j++) {
                if(dist(point[i], point[j]) <= 2 * r) {
                    merge(j, i);
                }
            } 
         }  
         if(find(0) == find(n + 1)) printf("Yes\n");
         else printf("No\n");
    }
    return 0;
}