← 返回题目列表

AtCoder · arc064_c

E. 宇宙射线

中文机器翻译题面 查看原题

分数: 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

最优路线如下:

e9c630751968b7051df5750b7ddc0e07.png

示例输入 2

-2 0 2 0
2
-1 0 2
1 0 2

示例输出 2

0.0000000000

最优路线如下:

fb82f6f4df5b22cffb868ce6333277aa.png

示例输入 3

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

示例输出 3

4.0000000000

最优路线如下:

d09006720c225cbe69eae3fd9c186e67.png