Luogu3958 [NOIP2017 提高组] 奶酪 题解

传送门：

• 洛谷
• GMOJ

前置知识

空间内两点 $P_1(x_1,y_1,z_1)$、$P2(x_2,y_2,z_2)$ 的距离公式如下：

$$\mathrm{dist}(P_1,P_2)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$$

题目大意

地面上有一块无限长宽的奶酪，高度为 $h$ ，其中下表面坐标为 $z=0$ ，上表面坐标为 $z=h$ 。

奶酪其中有 $n$ 个空洞，半径都为 $r$，给定每个空洞球心的坐标 $(x_i,y_i,z_i)$ 。如果某两个空洞相交或相切，则这两个空洞为互相连接的。求是否能从奶酪下面走到奶酪上面。（多测）

思路

显然，两个空洞如果互相连接，则它们球心的坐标之差一定 $\leq 2r$ 。

根据这个定理，我们求出每两个连接的空洞并记录。

for (int i = 1 ; i <= n ; ++i)
{
    for (int j = 1 ; j <= n ; ++j)
    {
        if (sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z)) <= r*2.0) //两个空洞相交或相切
        {
            v[i][j] = 1;
        }
    }   
}

并记录空洞是否与奶酪顶或奶酪底相交。如果与奶酪底相交，则添加到搜索起点集合中（这里用的是BFS，将其添加到队列中），如果与奶酪顶相交，则添加到搜索终点集合中。

if (a[i].z-r <= 0)
{
    q.push(i); //添加到搜索起点集合
}
if (a[i].z+r >= h)
{
    v[i][0]=1; //使用 0下标 表示奶酪顶
    v[0][i]=1;
}

开始 $BFS$ 搜索即可。

bool f=0;
while (!q.empty())
{
    int x=q.front();
    q.pop();
    if (vis[x]) continue; //已经搜索过的点不再搜索
    if (v[x][0]) //与奶酪顶相交
    {
        f=1;
        break;
    }
    vis[x]=1;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (v[x][i]&&!vis[i])
        {
            q.push(i);
        }
    }
}
//搜索结束
if (f) cout << "Yes" << endl;
else cout << "No" << endl;

复杂度分析

$1 \le n \le 1\times 10^3$，$1 \le h , r \le 10^9$，$T \le 20$，坐标的绝对值不超过 $10^9$。

由于我们有去重操作，所以至多循环 $n$ 次，但我们用了 $n^2$ 的复杂度来记录空洞是否连接，所以总复杂度为

$$O(Tn^2)$$

提示

不开 $long$ $long$ 见祖宗

完整代码

#include <bits/stdc++.h>
#define int long long //不开long long见祖宗
using namespace std;
struct node{
    int x,y,z;
}a[1005]; //a[i] 表示第 i 个空洞的坐标
bool v[1005][1005],vis[1005]; //v[i][j] 表示 i 与 j 相连
signed main()
{
    freopen("cheese.in","r",stdin);
    freopen("cheese.out","w",stdout);
    int T;
    cin >> T;
    while (T--)
    {
        memset(v,0,sizeof(v));
        memset(vis,0,sizeof(vis));
        int n,h,r;
        queue<int> q;
        cin >> n >> h >> r;
        for (int i = 1 ; i <= n ; ++i)
        {
            cin >> a[i].x >> a[i].y >> a[i].z;
            if (a[i].z-r <= 0)
            {
                q.push(i);
            }
            if (a[i].z+r >= h)
            {
                v[i][0]=1;
                v[0][i]=1;
            }
        }
        for (int i = 1 ; i <= n ; ++i)
        {
            for (int j = 1 ; j <= n ; ++j)
            {
                if (sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z)) <= r*2.0)
                {
                    v[i][j] = 1;
                }
            }   
        }
        bool f=0;
        while (!q.empty())
        {
            int x=q.front();
            q.pop();
            if (vis[x]) continue;
            if (v[x][0])
            {
                f=1;
                break;
            }
            vis[x]=1;
            for (int i = 1 ; i <= n ; ++i)
            {
                if (v[x][i]&&!vis[i])
                {
                    q.push(i);
                }
            }
        }
        if (f) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}