P3958 [NOIP2017 提高组] 奶酪——广搜

绝地灬酷狼 2023-01-14 14:00 163阅读 0赞

# 看原题：[P3958 \[NOIP2017 提高组\] 奶酪][P3958 _NOIP2017 _] #

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

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

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

空间内两点  P 1 ( x 1 , y 1 , z 1 ) P\_1(x\_1,y\_1,z\_1) P1(x1,y1,z1)、 P 2 ( x 2 , y 2 , z 2 ) P2(x\_2,y\_2,z\_2) P2(x2,y2,z2)的距离公式如下：

d i s t ( P 1 , P 2 ) = ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 + ( z 1 − z 2 ) 2 \\mathrm\{dist\}(P\_1,P\_2)=\\sqrt\{(x\_1-x\_2)^2+(y\_1-y\_2)^2+(z\_1-z\_2)^2\} dist(P1,P2)=(x1−x2)2\+(y1−y2)2\+(z1−z2)2

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

第一行，包含一个正整数 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

**说明/提示**  
**【输入输出样例 1 说明】**

![在这里插入图片描述][20210420211003645.png_pic_center]

第一组数据,由奶酪的剖面图可见：

第一个空洞在  ( 0 , 0 , 0 ) (0,0,0) (0,0,0) 与下表面相切；

第二个空洞在  ( 0 , 0 , 4 ) (0,0,4) (0,0,4) 与上表面相切；

两个空洞在  ( 0 , 0 , 2 ) (0,0,2) (0,0,2) 相切。

输出 `Yes`。

第二组数据,由奶酪的剖面图可见：

两个空洞既不相交也不相切。

输出 `No`。

第三组数据,由奶酪的剖面图可见：

两个空洞相交，且与上下表面相切或相交。

输出 `Yes`。

**【数据规模与约定】**

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

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

对于  80 % 80\\% 80% 的数据， 1 ≤ n ≤ 1 0 3 1 \\le n \\le 10^3 1≤n≤103 ， 1 ≤ h , r ≤ 1 0 4 1 \\le h , r \\le 10^4 1≤h,r≤104，坐标的绝对值不超过  1 0 4 10^4 104

对于  100 % 100\\% 100% 的数据， 1 ≤ n ≤ 1 × 1 0 3 1 \\le n \\le 1\\times 10^3 1≤n≤1×103， 1 ≤ h , r ≤ 1 0 9 1 \\le h , r \\le 10^9 1≤h,r≤109， T ≤ 20 T \\le 20 T≤20，坐标的绝对值不超过  1 0 9 10^9 109

# 题解 #

广搜，对我来说有一点难度。

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <queue>
    using namespace std;
    int shu, ch;
    bool tf;
    int dy() //读入优化，记得要判断负数
    { 
        shu = ch = 0, tf = true;
        while (ch < '0' || ch > '9')
            tf = ch == '-' ? false : true, ch = getchar();
        while (ch >= '0' && ch <= '9')
            shu = shu * 10 + ch - '0', ch = getchar();
        return tf ? shu : -shu;
    }
    struct POS //存储输入的点的坐标
    { 
        int x, y, z;
    } pos[2000];
    queue<int> bfs; //bfs所用的队列
    int lc;
    bool visit[2000]; //是否有到达过这个点
    struct Edge       //链表，我是模仿链式前向星来写的
    { 
        int t;
        int nexty;
    } edge[3000000];
    int head[2000];
    long long pf(int a) //平方，注意要int转long long
    { 
        return ((long long)a) * ((long long)a);
    }
    long long dis(int a, int b) //算出距离的平方
    { 
        return pf(pos[a].x - pos[b].x) + pf(pos[a].y - pos[b].y) + pf(pos[a].z - pos[b].z);
    }
    int cnt;
    void add(int a, int b) //链表加边
    { 
        cnt++;
        edge[cnt].t = b;
        edge[cnt].nexty = head[a];
        head[a] = cnt;
    }
    int main()
    { 
        int t = dy();
        int n, h, r;
        bool tf;
        while (t--)
        { 
            n = dy(), h = dy(), r = dy();
            for (int i = 0; i < n; i++)
            { 
                pos[i].x = dy();
                pos[i].y = dy();
                pos[i].z = dy();
            }
            while (!bfs.empty())
                bfs.pop();
            for (int i = 0; i < n; i++)
                visit[i] = false, head[i] = 0;
            cnt = 0; //初始化
            for (int i = 0; i < n; i++)
            { 
                for (int j = i + 1; j < n; j++)
                { 
                    if (dis(i, j) <= 4 * pf(r)) //如果两圆心距离小于2r（这里是平方形式，所以变成4*r^2），则它们可以互相到达
                    { 
                        add(i, j);
                        add(j, i); //互相加边
                    }
                }
            }
            tf = false; //tf即是否可以到达上面
            for (int i = 0; i < n && !tf; i++)
            { 
                if (pos[i].z <= r) //如果可以从底层进入
                { 
                    bfs.push(i);
                    visit[i] = true; //记得打上visit
                    if (h - pos[i].z <= r)
                        tf = true; //如果已经可以走到上层，则直接跳出
                }
            }
            while (!tf && !bfs.empty()) //bfs开始
            { 
                lc = bfs.front();
                bfs.pop();
                for (int i = head[lc]; i != 0 && !tf; i = edge[i].nexty) //遍历可以到达的点
                { 
                    if (!visit[edge[i].t]) //如果没有到达过
                    { 
                        bfs.push(edge[i].t);
                        visit[edge[i].t] = true;
                        if (h - pos[edge[i].t].z <= r)
                            tf = true; //如果已经到达上面，则跳出
                    }
                }
            }
            if (tf)
                printf("Yes\n");
            else
                printf("No\n"); //判断输出Yes还是No
        }
        return 0;
    }

[P3958 _NOIP2017 _]: https://www.luogu.com.cn/problem/P3958
[20210420211003645.png_pic_center]: /images/20221022/32a7c037564e488b9cf97fee5482e2a8.png