配点 : $600$ 点

問題文

$x$$y$ 平面があります。 すぬけ君は座標 $(x_s, y_s)$ から座標 $(x_t, y_t)$ まで移動しようとしています。 すぬけ君は好きな向きへ速さ $1$ で動くことができます。 なお、すぬけ君は大きさのない点と見なすことにします。

平面上には $N$ 個の円形のバリアが張ってあります。 $i$ 番目のバリアは中心が $(x_i, y_i)$ で半径が $r_i$ です。 バリアは互いに重なっていたり、互いを含んでいたりすることがあります。

平面上の各座標について、その座標がどのバリアの内部にも含まれない場合、その座標には宇宙線が降り注いでいます。

すぬけ君は移動中にできるだけ宇宙線を浴びたくないので、宇宙線を浴びる時間が最小になるように移動します。 すぬけ君が移動中に宇宙線を浴びる時間の最小値を求めてください。

制約

• 入力はすべて整数である。
• $-10^9 \leq x_s, y_s, x_t, y_t \leq 10^9$
• $(x_s, y_s)$ ≠ $(x_t, y_t)$
• $1 \leq N \leq 1,000$
• $-10^9 \leq x_i, y_i \leq 10^9$
• $1 \leq r_i \leq 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$

出力

すぬけ君が移動中に宇宙線を浴びる時間の最小値を出力せよ。 絶対誤差または相対誤差が $10^{-9}$ 以下ならば正解となる。

-2 -2 2 2
1
0 0 1

3.6568542495

たとえば、図のように移動すればよいです。

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

0.0000000000

たとえば、図のように移動すればよいです。

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

4.0000000000

たとえば、図のように移動すればよいです。