题解【洛谷P3958】[NOIP2017]奶酪

题面

题解

我们考虑使用一个并查集维护空洞之间的关系。

如果两个空洞能相互到达，那么它们的祖先也是相同的。

枚举从哪一个空洞开始，能否到达奶酪的上表面。

如果能到达就输出Yes，否则输出No。

注意开long long。

代码

#include <bits/stdc++.h>
#define itn int
#define int long long
#define gI gi

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int maxn = 1003;

bool fl = false;
int t, n, m, h, r, fa[maxn], x[maxn], y[maxn], z[maxn];

inline bool getdis(int x, int y, int z)
{
    if (x * x + y * y + z * z <= 4 * r * r) return true;//计算能否互相到达
    return false;
}

inline void kz(int u)//进行扩展
{
    if (!fl) return;//已经有解了就直接返回
    if (z[u] + r >= h)//到达了上表面
    {
        fl = false;
        return;
    }
    for (int i = 1; i <= n; i+=1)
    {
        if (fa[i] == 1) continue;//能够互相到达就不要再计算了
        if (getdis(x[i] - x[u], y[i] - y[u], z[i] - z[u]))//可以从u到i
        {
            fa[i] = 1;//记录祖先
            kz(i);//扩展i
        }
    }
}

inline void solve()
{
    for (int i = 1; i <= n; i+=1)
    {
        if (z[i] <= r)//可以从下表面开始
        {
            fa[i] = 1;//记录祖先
            kz(i);//进行扩展
        }
    }
}

signed main()
{
    t = gi();
    while (t--)
    {
        n = gi(), h = gi(), r = gi();
        for (int i = 1; i <= n; i+=1) fa[i] = 0;//初始化
        for (int i = 1; i <= n; i+=1)
        {
            x[i] = gi(), y[i] = gi(), z[i] = gi();
        }
        fl = true;
        solve();
        if (fl) puts("No");
        else puts("Yes");//输出
    }
    return 0;
}