Atcoder 题解

Atcoder Beginner Contest 259 problem D 题解

题目链接：点我

题目大意

在平面直角坐标系中给定$N$个圆，第$i$个圆的圆心坐标为$(x_i,y_i)$，半径为$r_i$。给定两个坐标$(s_x,s_y),(t_x,t_y)$，问能否从$(s_x,s_y)$点通过这些圆的圆周走到点$(t_x,t_y)$。

对于每个测试点，第一行输入$N$，第二行输入$s_x,s_y,t_x,t_y$，其后$N$行，每行输入$x_i,y_i,r_i$。

如果能到达，输出"Yes";否则输出"No"。

样例输入1

4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3

样例输出1

Yes

样例解释1

下面是一种从$(0,-2)$走到$(3,3)$的方法：

• 从$(0,-2)$，我们可以通过第一个圆移动到$(1,- \sqrt3 )$的位置；
• 从$(1,- \sqrt3 )$，我们可以通过第二个圆移动到$(2,2)$的位置；
• 从$(2,2)$，我们可以通过第三个圆移动到$(3,3)$的位置。

样例输入2

3
0 1 0 3
0 0 1
0 0 2
0 0 3

样例输出2

No

样例解释2

这种情况下是不可能达到的。所以输出"No"。

数据范围

• $1 \leq N \leq 3000$
• $-10^9 \leq x_i,y_i \leq 10^9$
• $1 \leq r_i \leq 10^9$
• 点$(s_x,s_y)$和点$(t_x,t_y)$都至少会落在一个圆的圆周上。
• 所有输入均为整型数。

解析

乍一看，这个题仿佛没什么思路。

不过仔细思考一下，就可以发现：如果我们将所有圆编号并看做一个点，那么从一个圆的圆周能走到另一个圆的圆周，就是等价于能从这个点走到那个点。

于是，我们双层枚举所有圆，判断两个圆之间是否相交。如果相交，那么两点之间就有一条边。判断完后，就可以一遍简单的深搜找到$(s_x,s_y)$所在的圆能否到达$(t_x,t_y)$所在的圆。

起点与终点可能会位于多个圆上，不过这并没有影响。只需要找到其中一个圆即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3005;
int n;
int sx,sy,tx,ty;
int x[N],y[N],r[N];
vector<int> v[N]; //邻接矩阵
bool vis[N];
int s,t;
inline bool dfs(int s){
    vis[s]=1;
    if(s==t) return 1;
    for(int i=0;i<v[s].size();i++){
        if(vis[v[s][i]])continue;
        if(dfs(v[s][i])) return 1;
    }
    return 0;
}
signed main()
{
    cin>>n;
    cin>>sx>>sy>>tx>>ty;
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld",&x[i],&y[i],&r[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            int d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); //d为两圆心之间的距离 的平方
            if(d>(r[i]+r[j])*(r[i]+r[j]) || d<(r[i]-r[j])*(r[i]-r[j])) continue;
            //如果圆心距大于两圆半径之和，则两圆相离，这种情况下两圆无法相互到达；
            //如果圆心距小于两圆半径之差，则大圆包含着小圆，这种情况下两圆也无法相互到达；
            v[i].push_back(j);v[j].push_back(i);
            //如果可以相互到达，则点i与点j有双向边。
        }
    for(int i=1;i<=n;i++){
        if((x[i]-sx)*(x[i]-sx)+(y[i]-sy)*(y[i]-sy)==r[i]*r[i]) s=i;
        if((x[i]-tx)*(x[i]-tx)+(y[i]-ty)*(y[i]-ty)==r[i]*r[i]) t=i;
    }
    //找到起点与终点所在圆的编号
    if(dfs(s)) cout<<"Yes"; //小dfs一下~
    else cout<<"No";
    return 0;
}

完结撒花~