所谓过河

NC221819. 所谓过河

描述

sky一到饭点便冲向了食堂，刚学会魔法的lzh见状，在他和食堂之间变出了一条无限长的大河( 宽当然是有限的 )。
幸运的是，lzh的魔法还不够精妙，长河中还留有 $N$ 个残余的圆形石头（重叠部分厚度不计），
sky可以踩在上面过河，当然他不能在石头之间跳远，只有两个圆形石头相交（有重叠部分或紧贴）他才能在这两块石头上来回移动，
同样他只能通过与岸边相交的石头才能上岸或者进入河中。 sky想知道他能不能到达河对面，请你帮帮他。

输入描述

第一行包括两个整数  ， ,表示石头的个数和河的宽度。
sky所在的河岸边可以看作 的直线，河对面的岸可看作  的直线。
接下来  行每一行包括三个整数  ；分别表示每块石头的圆心坐标以及半径，保证所有石头的圆心都在河中。

输出描述

如果sky能到河对面，输出”Yes“,反之输出”No“

示例1

输入:

2 3
1 1 1
1 3 1

输出:

Yes

示例2

输入:

2 3
1 1 1
1 4 1

输出:

No

示例3

输入:

输出:

Yes

示例4

输入:

1 2
2 1 1

输出:

Yes

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 4ms, 内存消耗: 436K, 提交时间: 2021-09-12 17:39:12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=1e5+10;

ll x[maxn],y[maxn],r[maxn],vis[maxn],flag=0,n,h;

void dfs(int u){
	vis[u]=1;
	if(y[u]+r[u]>=h){
		flag=1;
		return;
	}
	for(int v=0;v<n;v++){
		if(!vis[v]){
			ll dis=(x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]);
			if(dis<=(r[u]+r[v])*(r[u]+r[v])) dfs(v);
		}
	}
}
int main(){
    cin>>n>>h;
	for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>r[i];
	for(int i=0;i<n;i++){
        if(flag) break;
		if(y[i]<=r[i]) dfs(i);
	}
	cout<<(flag?"Yes":"No")<<endl;
	return 0;
 }

上一题

下一题

详情