AI题库 · C/C++编程八级题库
题目分享 #12842
能量护盾
题目描述
在一处被宇宙射线笼罩的星域中,你驾驶着一艘小型探索飞船,需要从坐标 (xs,ys) 航行到坐标 (xt,yt)。
飞船可以以速度 1 向任意方向移动,自身视为一个点。
星域中分布着 N 个圆形能量护盾,第 i 个护盾的圆心为 (xi,yi),半径为 ri。护盾之间可能相互重叠,也可能存在包含关系。
飞船一旦进入某个护盾的内部,就能免受宇宙射线的伤害。若一个点不在任何护盾内部,则飞船会持续受到宇宙射线的照射。
你的目标是:在从起点到终点的航行过程中,尽可能减少受到宇宙射线照射的总时间。
请你计算这个最小照射时间。
输入格式
第一行,四个整数 xs,ys,xt,yt,分别表示起点和终点的坐标。
第二行,一个整数 N,表示圆形护盾的数量。
接下来 N 行,每行三个整数 xi,yi,ri,描述第 i 个护盾的圆心坐标和半径。
输出格式
输出一个实数,表示受到宇宙射线照射的最小时间,保留 10 位小数。
输入样例#1
-2 -2 2 2 1 0 0 1
输出样例#1
3.6568542495
输入样例#2
-2 0 2 0 2 -1 0 2 1 0 2
输出样例#2
0.0000000000
输入样例#3
4 -2 -2 4 3 0 0 2 4 0 1 0 4 1
输出样例#3
4.0000000000
说明提示
−109≤xs,ys,xt,yt≤109
(xs,ys)≠(xt,yt)
1≤N≤1000
−109≤xi,yi≤109
1≤ri≤109
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。