「Luogu P3958」奶酪

Description

共 $T$ 组数据。在一个三维坐标系上，有 $n$ 个球体，坐标分别为 $(x_i, y_i, z_i)$，半径为 $r$ 。现在从 $z$ 轴的 $0$ 位置出发，所经过的位置一定要有球体覆盖，求能否到达 $z$ 轴的 $h$ 位置。

$(1 \leq n \leq 10^3,1 \leq h,r \leq 10^9,T \leq 20$，坐标的绝对值不超过 $10^9)$

Source

[Luogu]P3958

Solution

考虑用 并查集 维护球体形成的连通块。

如何判断两个球体是否连通？

这就要用到三维空间中的欧式距离公式：

$$\left | AB \right | = \sqrt{\left ( x_2 - x_1 \right )^2 + \left ( y_2 - y_1 \right )^2 + \left ( z_2 - z_1 \right )^2}$$

若两个球体球心之间的欧式距离 $|AB| \leq 2r$，则说明这两个球体相交或者相切，可以把它们合并到同一个连通块中。

对于每个连通块，如果与底面和顶面都相连，就能够到达，反之则不行。时间复杂度为 $O(n^2)$ 。

由于求欧式距离时存在精度误差，我们可以将不等式两边开平方，得到

$$\left | AB \right |^2 \leq 4r^2$$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e3;
int t, n, h, r, x[MAXN + 5], y[MAXN + 5], z[MAXN + 5], d[MAXN + 5], u[MAXN + 5];

inline LL dist(int i, int j) {//三维空间内两点间欧式距离的平方
    return (LL) (x[i] - x[j]) * (x[i] - x[j]) + (LL) (y[i] - y[j]) * (y[i] - y[j])
    + (LL) (z[i] - z[j]) * (z[i] - z[j]);
}

struct ufSet {
    int fa[MAXN + 5];
    
    ufSet(int n) {
        for (int i = 1; i <= n; ++i) fa[i] = i; 
    }
    int find(int x) {
        return x != fa[x] ? fa[x] = find(fa[x]) : x;
    }
    inline void merge(int x, int y) {
        fa[find(x)] = find(y);
    }
};

int main() {
    for (read(t); t; --t) {
        read(n), read(h), read(r);
        for (int i = 1; i <= n; ++i) read(x[i]), read(y[i]), read(z[i]);
        ufSet s(n);
        memset(d, 0, sizeof (d));
        memset(u, 0, sizeof (u));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j < i; ++j)
                if (dist(i, j) <= (LL) 4 * r * r)
                //为避免精度误差，这里对不等式两边开平方
                    s.merge(i, j);//合并到同一个连通块中
        bool flag = 0;
        for (int i = 1; i <= n; ++i) {
            if (z[i] - r <= 0) d[s.find(i)] = 1;//与底面相连
            if (z[i] + r >= h) u[s.find(i)] = 1;//与顶面相连
            if (d[s.find(i)] && u[s.find(i)]) {//如果一个连通块与底面和顶面都相连 
                flag = 1;
                break;
            }
        }
        puts(flag ? "Yes" : "No");
    }
    return 0;
}