题目描述

时空限制

CPU占用时长: 1秒

内存使用限制: 512MB

问题描述

现有一块大奶酪，它的高度为 hh，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z=0z=0，奶酪的上表面为 z=hz=h。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

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

输入格式

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

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

接下来是 T 组数据，每组数据的格式如下： 第一行包含三个正整数 n,h,r，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。

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

输出格式

T 行，分别对应 T 组数据的答案，如果在第 i组数据中，Jerry 能从下表面跑到上表面，则输出：

YES

不能，则输出：

NO

输入输出样例

输入样例：

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

数据范围与提示

对于 20% 的数据，n=1，1≤h，r≤10^4，坐标的绝对值不超过 10^4。

对于 40%的数据，1≤n≤8，1≤h，r≤10^4，坐标的绝对值不超过 10^4。

对于 80%的数据，1≤n≤10^3，1≤h，r≤10^4，坐标的绝对值不超过 10^4。

对于 100% 的数据，1≤n≤10^3，1≤h，r≤10^9，T≤20，坐标的绝对值不超过 10^9。

算法实现（C++）

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

/*
 * 奶酪问题
 * 
 * 题目描述：
 * 在3D空间中有一块高度为h的奶酪，其中有n个球形洞穴，每个洞穴的半径都是r
 * 需要判断是否能从奶酪的下表面穿透到上表面
 * 
 * 解题思路：
 * 1. 用并查集维护洞穴之间的连通性
 * 2. 如果两个洞穴之间的距离 <= 2r，则它们相互连通
 * 3. 找出与下表面相交的洞穴和与上表面相交的洞穴
 * 4. 如果存在某个洞穴与下表面相交，且与某个与上表面相交的洞穴连通，则可以穿透
 */

// 并查集数据结构，用于维护洞穴之间的连通关系
struct UnionFind {
    vector<int> f;  // 父节点数组
    
    // 构造函数：初始化n个节点，每个节点的父节点都是自己
    UnionFind(int n): f(n) {
        for (int i = 0; i < n; i++) f[i] = i;
    }
    
    // 查找操作：找到x所在集合的根节点，并进行路径压缩优化
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    
    // 合并操作：将x和y所在的集合合并
    void unite(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) f[fx] = fy;  // 将fx的根节点指向fy的根节点
    }
};

// 洞穴结构体，存储洞穴的球心坐标
struct Hole {
    double x, y, z;  // 洞穴球心的三维坐标
};

int main() {
    int T;  // 测试用例数量
    cin >> T;
    
    while (T--) {
        int n;        // 洞穴数量
        double h, r;  // h为奶酪高度，r为洞穴半径
        cin >> n >> h >> r;
        
        // 读入所有洞穴的球心坐标
        vector<Hole> holes(n);
        for (int i = 0; i < n; i++) {
            cin >> holes[i].x >> holes[i].y >> holes[i].z;
        }
        
        // 初始化并查集，用于维护洞穴之间的连通关系
        UnionFind uf(n);

        // 检查每对洞穴是否可以连通
        // 如果两个球心距离 <= 2r，则认为两个洞穴可以连通，合并到同一集合
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                // 计算两个洞穴球心之间的欧几里得距离
                double dx = holes[i].x - holes[j].x;
                double dy = holes[i].y - holes[j].y;
                double dz = holes[i].z - holes[j].z;
                double dist = sqrt(dx*dx + dy*dy + dz*dz);
                
                // 如果距离小于等于2r，说明两个洞穴相交或相切，可以连通
                if (dist <= 2*r + 1e-8) { // 加上微小误差避免浮点数精度问题
                    uf.unite(i, j);
                }
            }
        }

        // 分别找出与底部表面和顶部表面相交的洞穴
        vector<int> bottom, top;  // bottom存储与下表面相交的洞穴，top存储与上表面相交的洞穴
        
        for (int i = 0; i < n; i++) {
            // 球与下表面相交或相切的条件：球心z坐标减去半径 <= 0
            if (holes[i].z - r <= 0) bottom.push_back(i);
            
            // 球与上表面相交或相切的条件：球心z坐标加上半径 >= h
            if (holes[i].z + r >= h) top.push_back(i);
        }

        bool can = false;  // 标记是否可以从下表面穿透到上表面
        
        // 判断是否存在某对洞穴，分别与底部和顶部相交，并且在同一连通分量中
        for (int b : bottom) {           // 遍历所有与下表面相交的洞穴
            for (int t : top) {          // 遍历所有与上表面相交的洞穴
                if (uf.find(b) == uf.find(t)) {  // 如果两个洞穴在同一连通分量中
                    can = true;          // 说明可以从下表面穿透到上表面
                    break;
                }
            }
            if (can) break;  // 一旦找到可行方案就提前结束
        }
        
        // 输出结果
        cout << (can ? "Yes" : "No") << endl;
    }
    return 0;
}

为孩子们讲解奶酪洞洞冒险

大冒险：小老鼠 Jerry 的奶酪之旅

想象一块超级大的奶酪，像一座巨大的奶酪山！它很高，底部是地面（我们叫它 z=0），顶部是天花板（我们叫它 z=h）。奶酪的宽度和长度超级大，像是没有边际。这块奶酪里有很多泡泡洞，就像一个个圆圆的气球，里面是空的，每个洞都有一个中心点。

有一只小老鼠 Jerry 站在奶酪的底部（地面）。它知道奶酪里所有泡泡洞的位置。Jerry 想知道：能不能通过这些洞洞，从奶酪的底部跑到顶部？它只能在洞里跑，而且只有当两个洞碰在一起（像朋友手拉手）时，Jerry 才能从一个洞跳到另一个洞。还有：

• 如果一个洞碰到奶酪的底部（地面），Jerry 可以从地面钻进这个洞。
• 如果一个洞碰到奶酪的顶部（天花板），Jerry 可以从这个洞爬到顶部。

Jerry 的目标是：不破坏奶酪，找到一条通过洞洞的路，从底部跑到顶部！

怎么知道哪些洞是朋友？（朋友清单的魔法）

为了知道哪些洞是连在一起的，我们用一个特别的工具，叫**“朋友清单”**（这就是代码里的 UnionFind）。你可以把它想象成 Jerry 的冒险笔记本，记录哪些泡泡洞是“朋友”，属于同一个“洞洞团”。

第一步：每个洞都是孤单的

一开始，每个泡泡洞都是自己的老大。想象每个洞有一个名字（比如洞1、洞2、洞3）。Jerry 在笔记本里写：

• 洞1 → 洞1
• 洞2 → 洞2
• 洞3 → 洞3

这表示每个洞都是一个单独的小团体，Jerry 还不知道它们能不能连起来。

第二步：找到洞洞朋友

如果两个洞靠得很近（它们的中心点距离小于或等于它们大小的两倍，像是两个气球刚好碰到或重叠），它们就成了朋友！Jerry 会在笔记本里更新，说它们在同一个洞洞团。比如：

• 如果洞1和洞2碰在一起，Jerry 写：“洞1的老大是洞2。”
• 后来，如果洞2又碰到了洞3，Jerry 写：“洞2的老大是洞3。”

现在，洞1、洞2和洞3都在同一个洞洞团，洞3是“领队”。

第三步：检查领队

想知道两个洞是不是在同一个洞洞团？Jerry 就问：“你的领队是谁？”它顺着笔记本找：

• 如果洞1的老大是洞2，洞2的老大是洞3，那么洞1的领队就是洞3。
• 为了下次问得更快，Jerry 直接改笔记本，让洞1直接指向洞3。这就像说：“嘿，洞1，记住你的领队是洞3！”

这个“捷径”小技巧叫路径压缩，它让 Jerry 找朋友变得超级快。

这对 Jerry 的冒险有什么帮助？

Jerry 用朋友清单来计划它的奶酪冒险，步骤是这样的：

1. 找碰在一起的洞：Jerry 检查每对洞。如果它们靠得够近（中心点距离小于两倍大小），就把它们记在同一个洞洞团。
2. 检查底部和顶部：Jerry 找： 贴着奶酪底部（地面）的洞（它们的底部边碰到地面，z 坐标减去洞的大小 ≤ 0）。 贴着奶酪顶部（天花板）的洞（它们的顶部边碰到天花板，z 坐标加上洞的大小 ≥ h）。
3. 找一条路：Jerry 问：“有没有一个贴着底部的洞和一个贴着顶部的洞是在同一个洞洞团？”如果有，Jerry 就能从底部钻进洞，跳到顶部！

一个有趣的例子

假设奶酪高5个单位，里面有3个泡泡洞，每个洞大小是1个单位：

• 洞1在 (1, 1, 1)
• 洞2在 (2, 2, 2)
• 洞3在 (1, 1, 3)

Jerry 检查它们有没有碰在一起：

• 洞1和洞2靠得够近，成了朋友。

• 洞2和洞3也靠得够近，也成了朋友。

在笔记本里：

• 洞1 → 洞2 → 洞3（它们都在一个洞洞团，洞3是领队）。

现在：

• 洞1贴着底部（它的底部边在 1 - 1 = 0，正好是地面）。
• 洞3贴着顶部（它的顶部边在 3 + 1 = 4，接近天花板的5）。
• 因为洞1和洞3在同一个洞洞团，Jerry 可以从地面钻进洞1，跳到洞2，再跳到洞3，最后爬到顶部！所以答案是：“是的，Jerry 能跑到顶部！”

为什么这很酷？

朋友清单（并查集）就像 Jerry 的魔法笔记本，帮它快速知道哪些洞是连在一起的，不用每次都重新检查。它又快又聪明，就像 Jerry 有一个超级侦探帮它找路！

我们来画画看！

为了更好玩，我们可以把泡泡洞画成彩色的球，放在奶酪里。碰在一起的洞用线连起来，奶酪的底部画成绿色，顶部画成黄色。

我们学到了什么？

• 我们用“朋友清单”（并查集）来记录哪些泡泡洞是连在一起的。
• 我们检查 Jerry 能不能从贴着底部的洞跳到贴着顶部的洞，通过它们的洞洞团。
• 电脑用这个方法很快就能帮 Jerry 找到路，哪怕奶酪里有好多洞！