分数: 600 点
问题陈述
关于 xy- 飞机,Snuke 将从该点出发 (x_s, y_s) 说到点子上 (x_t, y_t)。 他可以向任意方向快速移动 1。 在这里,我们将他视为一个没有大小的点。
有 N 飞机上部署的圆形障碍物。 的中心和半径 i第一个障碍是 分别为 (x_i, y_i) 和 r_i。 障碍可以重叠或相互包含。
如果平面上的点不在任何障碍物内,则该点会暴露在宇宙射线下。
Snuke 希望在旅途中尽可能避免接触宇宙射线。 求出他在旅行期间暴露于宇宙射线的最短可能持续时间。
约束
- 所有输入值均为整数。
- -10^9 ≤ x_s, y_s, x_t, y_t ≤ 10^9
- (x_s, y_s) ≠ (x_t, y_t)
- 1≤N≤1,000
- -10^9 ≤ x_i, y_i ≤ 10^9
- 1 ≤ r_i ≤ 10^9
输入
输入由标准输入按以下格式给出:
x_s y_s x_t y_t N x_1 y_1 r_1 x_2 y_2 r_2 : x_N y_N r_N
输出
打印 Snuke 在旅行期间暴露于宇宙射线的最短可能持续时间。 如果绝对或相对误差最多为,则输出被认为是正确的 10^{-9}.
示例输入 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
最优路线如下: