题目描述

在 $x$ $y$ 平面上，有一个名为すぬけ君的小点，他想从坐标 $(x_s,\ y_s)$ 移动到坐标 $(x_t,\ y_t)$。すぬけ君可以以速度 $1$ 向任意方向移动。这里，すぬけ君被视为没有大小的点。

平面上有 $N$ 个圆形屏障。第 $i$ 个屏障的圆心为 $(x_i,\ y_i)$，半径为 $r_i$。这些屏障之间可能会重叠，也可能互相包含。

对于平面上的每一个坐标，如果该坐标不在任何一个屏障的内部，则该坐标会被宇宙射线照射。

すぬけ君希望在移动过程中尽可能少地暴露在宇宙射线下。请你求出すぬけ君在移动过程中暴露在宇宙射线下的最短时间。

输入格式

输入以如下格式从标准输入读入。

$x_s$ $y_s$ $x_t$ $y_t$ $N$ $x_1$ $y_1$ $r_1$ $x_2$ $y_2$ $r_2$ $\cdots$ $x_N$ $y_N$ $r_N$

输出格式

请输出すぬけ君在移动过程中暴露在宇宙射线下的最短时间。只要绝对误差或相对误差不超过 $10^{-9}$，即可视为正确。

样例 1

输入

-2 -2 2 2
1
0 0 1

输出

3.6568542495

样例 2

输入

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

输出

0.0000000000

样例 3

输入

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

输出

4.0000000000

说明/提示

限制条件

• 所有输入均为整数。
• $-10^9\ <=\ x_s,\ y_s,\ x_t,\ y_t\ <=\ 10^9$
• $(x_s,\ y_s) \neq (x_t,\ y_t)$
• $1\ <= N <= 1,000$
• $-10^9\ <=\ x_i,\ y_i\ <=\ 10^9$
• $1\ <= r_i <= 10^9$

样例解释 1

例如，可以如图所示进行移动。

样例解释 2

例如，可以如图所示进行移动。

样例解释 3

例如，可以如图所示进行移动。

由 ChatGPT 4.1 翻译