奶酪

奶酪 1 2

题目描述

现有一块大奶酪，它的高度为 $h$，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。

我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 $z=0$，奶酪的上表面为 $z=h$。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。

如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去?

空间内两点 $P_1(x_1,y_1,z_1)、P_2(x_2,y_2,z_2)$ 的距离公式如下：

$$dist(P_1,P_2) = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$$

输入格式

每个输入文件包含多组数据。

输入文件的第一行，包含一个正整数 $T$，代表该输入文件中所含的数据组数。

接下来是 $T$ 组数据，每组数据的格式如下：

第一行包含三个正整数 $n，h$ 和 $r$，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。

接下来的 $n$ 行，每行包含三个整数 $x、y、z$，两个数之间以一个空格分开，表示空洞球心坐标为 $(x,y,z)$。

输出格式

输出文件包含 $T$ 行，分别对应 $T$ 组数据的答案，如果在第 $i$ 组数据中，Jerry 能从下表面跑到上表面，则输出 Yes，如果不能，则输出 No。

数据范围

$1 \le n \le 1000$,
$1 \le h,r \le 10^9$,
$T \le 20$,
坐标的绝对值不超过$10^9$

输入样例：

3 
2 4 1 
0 0 1 
0 0 3 
2 5 1 
0 0 1 
0 0 4 
2 5 2 
0 0 2 
2 0 4

输出样例：

Yes
No
Yes

思路

并查集

由于奶酪上的球形空洞数量较少（$1 \le n \le 1000$），因此，可以双重循环枚举每两个球形空洞是否连通（即两个球是否相交或相切）。

若是，则可以merge两者。但由于题目问的是Jerry是否能从奶酪的下表面经由球形空洞从上表面出去，因此要建立两个虚拟的点，分别表示球的上下表面，他们与每个球的距离就是球心到平面的距离，如果相交或相切，也合并。最后就是询问上下表面是否连通，用same函数判断即可。

搜索（摘自洛谷题解）

这道题可以用 dfs 做，将空洞看为点，相切或相交则看作连边。

首先处理数据，看哪些空洞相切或相交，即两者球心距离小于半径 $r$，就将他们连边。

如果该空洞与下表面相切，就代表可以从该空洞开始搜索。

如果该空洞与上表面相切，就代表搜到该空洞即代表搜索通过，输出 yes。

所有路试完后仍未输出 yes，输出 no。

最后，多测一定要清空！

CODE

并查集

struct DSU
{
    vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {init(n);}
    
    void init(int n) 
    {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }
    
    int find(int x) 
    {
        while (x != f[x])
            x = f[x] = f[f[x]];
        return x;
    }
    
    bool same(int x, int y) {return find(x) == find(y);}
    
    bool merge(int x, int y) 
    {
        x = find(x);
        y = find(y);
        if (x == y) 
            return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {return siz[find(x)];}
};

struct P
{
    int x, y, z;
};

double dist(P a, P b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}

void solve()
{
    int n, h, r;
    cin >> n >> h >> r;
    vector<P> v(n + 1);
    for (int i=1;i<=n;i++)
        cin >> v[i].x >> v[i].y >> v[i].z;

    DSU dsu(n + 2);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i != j && dist(v[i], v[j]) <= 2 * r)
                dsu.merge(i, j);
    for (int i=1;i<=n;i++)
    {
        if (v[i].z <= r)
            dsu.merge(i, n + 1);
        if (h - v[i].z <= r)
            dsu.merge(i, n + 2);
    }
    cout << (dsu.same(n + 1, n + 2) ? "Yes" : "No") << _endl;
}