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

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

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

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

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

空间内两点 P1(x1,y1,z1)、P2(x2,y2,z2)的距离公式如下：

输入格式：

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

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

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

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

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

输出格式：

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

数据范围：

1≤n≤1000
1≤h,r≤1e9,
T≤20,
坐标的绝对值不超过1e9

输入样例：

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

分析步骤：

  第一：拿到这道题我们就可以知道，这是一道关于通道的问题，你要判断是否有一条从底部可以走到上表面的路径，如果有就成功了。所以看到这里我们就可以想到，将各个圆心的点判断是否能链接到一起，，如果可以就把他们放到一个集合之中。由此可以知道运用并查集。通过并查集，将两两相交或相切的两个空洞连在一起，然后再判断在同一个并查集中的点的最高位和最低为是否能够到达奶酪的顶和底即可。

  第二：书写主函数，构建整体架构：

             将相应的只输入进去，将并查集数组自我更新数值，意义是将自己的父节点定义为自己。

             随后输入横，纵，高的坐标，将其收入进  q  数组 。由此我们首先要判断是否有节点和底部 和 上表面连接在一起，如果有的话则将其进行压缩路径 p[ find(i) ] = find(0)意思是 i 的根节点的父节点 是 0 的根节点  ；  p[ find(i) ] = find(n + 1)意思是 i 的根节点的父节点 是 n+1 的根节点

cin>>t;
    while(t--){
        
    cin>>n>>h>>r;
    for(int i = 0 ; i <= n +1 ; i ++) p[i] = i;
    for(int i = 1 ; i <= n ; i ++){
      int x, y, z;
      cin>>x>>y>>z;
      q[i] = {x,y,z};
      if(abs(z) <= r) p[find(i)] = find(0);
      if(abs(z - h) <= r) p[find(i)] = find(n+1);
    }

               随后遍历每一个点 ， 判断他们是不是相交或者相切，如果是的话 则将 i 的根节点的父节点 改为 j 的父节点

               最后判断底部的节点0 和 上表面的节点n+1 是否在同一个集合，如果是则代表他们之中必定有个通道，可以从底部道顶端，于是输出yes。

    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j < i ; j++){
            LL sx = q[i].x - q[j].x;
            LL sy = q[i].y - q[j].y;
            LL sz = q[i].z - q[j].z;
            if(sx*sx+sy*sy+sz*sz <= 4*(LL)r*r)
            p[find(i)] = find(j);
        }
    }
    
    if (find(0) == find(n + 1)) puts("Yes");
        else puts("No");
    
 

  第三：书写find 函数

             如果 x 的 根节点 是自己的话就返回

             如果不是的话则进行状态压缩，将x的父节点的父节点的值 赋予 x的父节点，这样在这一条路径下的点都聚集在根节点处了

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

  第四：这是我给大家画的样例图片，大家可以好好照着理解一下，理解一下什么是路径压缩，他是运用递归的思想，不断向上去寻找最根节点的根节点在哪里 ， 找到了之后我们就依次返回，最终将路径上的每个点的父节点都变为根节点 

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;

using namespace std;

const int N = 1100;

struct node{
    int x, y, z;
}q[N];
int p[N];
int t,n,r,h;


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




int main()
{
    cin>>t;
    while(t--){
        
    cin>>n>>h>>r;
    for(int i = 0 ; i <= n +1 ; i ++) p[i] = i;
    for(int i = 1 ; i <= n ; i ++){
      int x, y, z;
      cin>>x>>y>>z;
      q[i] = {x,y,z};
      if(abs(z) <= r) p[find(i)] = find(0);
      if(abs(z - h) <= r) p[find(i)] = find(n+1);
    }
    
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j < i ; j++){
            LL sx = q[i].x - q[j].x;
            LL sy = q[i].y - q[j].y;
            LL sz = q[i].z - q[j].z;
            if(sx*sx+sy*sy+sz*sz <= 4*(LL)r*r)
            p[find(i)] = find(j);
        }
    }
    
    if (find(0) == find(n + 1)) puts("Yes");
        else puts("No");
    
    }
    
    return 0;
}