十五 528. 奶酪 (并查集)

528. 奶酪 (并查集)

思路：大体就是并查集的模板，空洞数组从1到n，增加0作为下表面，n+1作为上表面，遍历所有空洞，若与上下表面相切或是相交就将i join 到0或n+1，然后再比较任意两个空洞，两者相切或是相交就join起来，最后判断0与n+1是否相连。

import java.util.*;

public class Main {
    private static int T, n, h, r;
    private static int[][] holes;
    private static int[] father;
    
    private static void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }
    
    private static int find(int u) {
        if (u == father[u]) {
            return u;
        } else {
            father[u] = find(father[u]);
            return father[u];
        }
    }
    
    private static boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
    
    private static void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return;
        }
        father[v] = u;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        while (T-- > 0) {
            n = sc.nextInt();
            h = sc.nextInt();
            r = sc.nextInt();
            father = new int[n + 2];
            init();
            
            holes = new int[n + 1][3];
            for (int i = 1; i <= n; i++) {
                holes[i][0] = sc.nextInt();
                holes[i][1] = sc.nextInt();
                holes[i][2] = sc.nextInt();
                if (Math.abs(holes[i][2]) <= r) {
                    join(i, 0);
                }
                if (Math.abs(holes[i][2] - h) <= r) {
                    join(i, n + 1);
                }
            }
            
            for (int i = 2; i <= n; i++) {
                for(int j = 1; j < i; j++) {
                    long dx = holes[i][0] - holes[j][0];
                    long dy = holes[i][1] - holes[j][1];
                    long dz = holes[i][2] - holes[j][2];
                    if (dx * dx + dy * dy + dz * dz <= 4 * (long) r * r) {
                        join(i, j);
                    }
                }
            }
            
            if (isSame(0, n + 1)) {
                System.out.println("Yes");
            }
            else {
                System.out.println("No");
            }
        }
    }
}