奶酪

#include <bits/stdc++.h>
using namespace std;
long long n, h, r;
int t;
int a[1005], b[1005]; // 分别记录和上下相连的点
bool flag;
int a1, b1;
int fa[1005];
long long x[1005], y[1005], z[1005];
int findfa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findfa(fa[x]);
}
void merge(int x, int y)
{
    int fax = findfa(x);
    int fay = findfa(y);
    fa[fax] = fay;
}
bool query(int x, int y)
{
    int fax = findfa(x);
    int fay = findfa(y);
    return fax == fay;
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> h >> r;
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        flag = false;
        a1 = b1 = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> x[i] >> y[i] >> z[i];
            if (z[i] <= r)
                a[++a1] = i;
            if (h - z[i] <= r)
                b[++b1] = i;
            for (int j = 1; j < i; j++)
                if (!query(i, j) && (x[i] - x[j]) * (x[i] - x[j]) +
                                            (y[i] - y[j]) * (y[i] - y[j]) +
                                            (z[i] - z[j]) * (z[i] - z[j]) <=
                                        (2 * r) * (2 * r))
                    merge(i, j);
        }
        for (int i = 1; i <= a1; i++)
            for (int j = 1; j <= b1; j++)
                if (query(a[i], b[j]))
                    flag = true;
        if (flag)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}
```---
title: " P3958. 奶酪"
---

```cpp
#include <bits/stdc++.h>
using namespace std;
long long n, h, r;
int t;
int a[1005], b[1005]; // 分别记录和上下相连的点
bool flag;
int a1, b1;
int fa[1005];
long long x[1005], y[1005], z[1005];
int findfa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findfa(fa[x]);
}
void merge(int x, int y)
{
    int fax = findfa(x);
    int fay = findfa(y);
    fa[fax] = fay;
}
bool query(int x, int y)
{
    int fax = findfa(x);
    int fay = findfa(y);
    return fax == fay;
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> h >> r;
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        flag = false;
        a1 = b1 = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> x[i] >> y[i] >> z[i];
            if (z[i] <= r)
                a[++a1] = i;
            if (h - z[i] <= r)
                b[++b1] = i;
            for (int j = 1; j < i; j++)
                if (!query(i, j) && (x[i] - x[j]) * (x[i] - x[j]) +
                                            (y[i] - y[j]) * (y[i] - y[j]) +
                                            (z[i] - z[j]) * (z[i] - z[j]) <=
                                        (2 * r) * (2 * r))
                    merge(i, j);
        }
        for (int i = 1; i <= a1; i++)
            for (int j = 1; j <= b1; j++)
                if (query(a[i], b[j]))
                    flag = true;
        if (flag)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}