【并查集】P3958 奶酪

P3958 奶酪

思路：

因为一开始就知道可以用并查集做，只是试着写了一下。

显然，如果两球相切/相交时是可以merge的，在全部尝试过merge之后再判断【与顶面相交的洞】和【与底面相交的洞】是否在同一集合内即可（也就是find(i)==find(j)）

卡在了两处地方：

一是没有让所有洞两两之间都尝试一下merge（总是在担心时间复杂度……但这样完全可以过），写成了merge(i,i+1)

二是不知道怎么判断最后得到的大集合是否能贯穿整个奶酪。其实只要先记录下能与底面相交和能与顶面相交的洞的编号，再枚举即可，也只是(O(n^2))而已，可以过的

int fa[maxn];
int down[maxn];
int up[maxn];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) fa[x] = y;
}

struct node {
    LL x, y, z;
}hole[maxn];

LL count(node k1,node k2) {
    LL dx = (k1.x - k2.x) * (k1.x - k2.x);
    LL dy = (k1.y - k2.y) * (k1.y - k2.y);
    LL dz = (k1.z - k2.z) * (k1.z - k2.z);
    return dx + dy + dz;
}

int main()
{
    //ios::sync_with_stdio(false);
    int t; cin >> t;while(t--){
        LL n, h, r;
        cin >> n >> h >> r;
        for (int i = 1; i <= n; i++)fa[i] = i;
        for (int i = 1; i <= n; i++) {
            cin >> hole[i].x >> hole[i].y >> hole[i].z;
        }

        int pos1 = 0;
        int pos2 = 0;

        for (int i = 1; i <= n; i++) {
            if (r >= hole[i].z) down[++pos1] = i;
            //与底面相交的洞
            if (r >= h - hole[i].z) up[++pos2] = i;
            //与顶面相交的洞
            //注意一个洞可能同时与两个面相交，不能写成else if
        }

        //遍历当前洞前面的所有洞，尝试连通
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if ((hole[i].x - hole[j].x) * (hole[i].x - hole[j].x) + (hole[i].y - hole[j].y) * (hole[i].y - hole[j].y) > r * r * 4) continue;
                if (count(hole[i], hole[j]) <= r * r * 4) {
                    merge(i, j);
                }
            }
        }

        //枚举所有与上下表面连通的洞
        int ok = 0;
        for (int i = 1; i <= pos1; i++) {
            for (int j = 1; j <= pos2; j++) {
                if (find(down[i]) == find(up[j])) {
                    ok = 1;
                    break;
                }
            }
            if (ok) break;
        }
        if (ok) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}