Hide

Problem B
くまのバーニーができたよ

Languages en ja
/problems/bearlymadeit/file/statement/ja/img-0001.jpg

バーニーは極地の冒険に迷い込んでしまいました。バーニーは物思いにふけっていて、突然気付きます。お母さんからあまりにも遠く迷い、氷棚に立ち往生しているのです。まだ遠くにお母さんを見ることができますが、唯一の帰り道は他の氷棚のグループを横断することで、それらすべては完全に円形です。バーニーは非常に怖がっていて、泳ぐことはできません。少し息子の悪戯に飽きながら、お母さんはバーニーを待つことにしました。またバーニーに自分で何とかさせることにしました。バーニーが家に帰るのを手伝ってくれますか?バーニーは急いでいます。

入力

  • 入力の最初の行には $4$ つの整数が含まれ、 $-10^6 \leq x_ b, y_ b, x_ m, y_ m \leq 10^6$、この $(x_ b, y_ b)$ がバーニーの場所であり $(x_ m, y_ m)$ がバーニーのお母さんが待っている場所です。

  • 次の行には $1 \leq n \leq 25$の整数が含まれています、これは氷棚の数です。

  • 後の行は次の通り。各行は $3$ つの整数を保持します: $-10^6 \leq x_ i, y_ i \leq 10^6$ かつ $1 \leq r_ i \leq 10^6$ 、シェルフの中心の座標と半径。氷棚は、距離が $r_ i$ あるいは $(x_ i, y_ i)$ より小さいすべての点で構成されています。

両方のクマは、バーニーが動き始めたときに、同じ氷棚にいました。氷棚は接触することも重なることもできます。

出力

バーニーがお母さんと再会するために進む最小限の距離。結果は最大で $10^{-6}$ の相対的な誤差でなければなりません。

もしバーニーが戻る方法がなければ、 “impossible” と出力します。 (このシナリオではバーニーの幸せを心配しなくても大丈夫。お母さんはバーニーを救うために泳ぐでしょう。)

\includegraphics[width=.4\textwidth ]{3.pdf}
図 1: 3番目のサンプルの入力値の図。
サンプル入力 1 サンプル出力 1
0 0 6 0
2
1 1 2
5 1 2
6.32455532034
サンプル入力 2 サンプル出力 2
0 0 7 0
2
1 1 2
6 1 2
impossible
サンプル入力 3 サンプル出力 3
0 0 1 3
3
0 -1 2
4 -1 3
2 3 2
4.269334912857045697