奶酪

其实思路很好想 就是看是否有与顶面有交点的球，是否与底面有交点的球，然后判断这两种球是否存在一队相互连通
思路很简单 但是一开始一直WA 因为我是按照z 从大到小排序 我从z最大的点开始扩展 每次更新有交点的两个球 但是这样我会忽略当前的球与其他球是否连通(因为我每次都更新球) 所以还是要使用并查集 但是一开始并查集也出现问题 这是因为我的合并出现问题 我的合并直接按照循环的顺序 因为我是按照z 从大到小排序 那么我理所应当将j的父节点的父节点修改为i的父节点 但是我是想要将低的与高的连接在一起 j的z轴高度肯定比i低 但是j的父节点的父节点的z轴高度不一定比i的父节点的低 这就是我合并的错误所在 所以我要按照父节点z轴高度进行合并
最后只需判断与底面有交点的球的父节点表示的球是否与顶面有交点就可以了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
ll h, r;
int n, p[N];

struct Node
{
  ll x, y, z;
} a[N];

int find(int x)
{
  if (x != p[x])
    p[x] = find(p[x]);
  return p[x];
}

void merge(ll x, ll y)
{
  ll i = find(x);
  ll j = find(y);
  if (i == j)
    return;
  if (a[i].z >= a[j].z)
    p[j] = i;
  else
    p[i] = j;
}

bool check(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2)
{
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2)) <= 2 * r;
}

int main()
{
  ios::sync_with_stdio(0), cin.tie(0);
  int t;
  cin >> t;
  while (t--)
  {
    cin >> n >> h >> r;
    for (int i = 1; i <= n; ++i)
      cin >> a[i].x >> a[i].y >> a[i].z;
    sort(a + 1, a + n + 1, [](const Node &u, const Node &v)
         { return u.z > v.z; });
    for (int i = 1; i <= n; ++i)
      p[i] = i;
    for (int i = 1; i < n; ++i)
    {
      ll x1 = a[i].x, y1 = a[i].y, z1 = a[i].z;
      for (int j = i + 1; j <= n; ++j)
      {
        ll x2 = a[j].x, y2 = a[j].y, z2 = a[j].z;
        if (check(x1, y1, z1, x2, y2, z2))
          merge(i, j);
        //明白了 j的根的z高度 不一定比 i的根的高度低 故原做法是错的
      }
    }
    bool flag = 0;
    for (int i = n; i >= 1; --i)
    {
      if (a[p[i]].z + r >= h && a[i].z - r <= 0)
      {
        flag = 1;
        break;
      }
    }
    if (flag)
      puts("Yes");
    else
      puts("No");
  }
}