AT_geocon2013_d 魔女

[problemUrl]: https://atcoder.jp/contests/geocon2013/tasks/geocon2013_d あなたは、川と緑に囲まれた小さいながらも豊かな王国の魔女です。 新しい王が王国を視察することを聞いたあなたは仲間と一緒に邪魔することにしました。 魔女は自分を中心とした円の内側に呪いをまき散らすことができます。 また、魔力が強い魔女は円の大きさをだんだん大きくすることが可能です。 王はこの円の中に入ると呪いを受けてしまうので避けながら移動しなければなりません。 王が出発地から目的地へ最短で移動するときにかかる時間を求めましょう。 ただし、王が呪いを受けることなく目的地に到着できないときは `Impossible` と出力してください。 入力は以下の形式で標準入力から与えられる。 > $ Sx\ Sy\ Gx\ Gy\ V\ N $ $ W1,x\ W1,y\ W1,r\ W1,v $ $ W2,x\ W2,y\ W2,r\ W2,v $ $ ... $ $ WN,x\ WN,y\ WN,r\ WN,v $ - 入力はすべて整数で与えられる。 - 1行目には出発地の座標 $ Sx\ Sy $ 、目的地の座標 $ Gx\ Gy $ 、王が1分間に移動する距離 $ V $ 、魔女の人数 $ N $ が空白区切りで与えられる。 - 2行目からN+1行目には、魔女の座標 $ Wi,x\ Wi,y $ 、王が出発する時点での呪いの半径 $ Wi,r $ 、呪いの半径が1分間で広がる距離 $ Wi,v $ が空白区切りで与えられる。 - 王が出発してから $ t $ 分後の呪いの半径は $ Wi,r\ +\ Wi,v\ *\ t $ となる。例えば、 $ Wi,r\ =\ 1,\ Wi,v\ =\ 2 $ の場合、 $ 0.5 $ 分後に呪いの半径は $ 2 $ となる。 - 呪いの半径は連続的に大きくなる。 - 出発地・到着地は王が出発する時点で呪い受ける範囲内ではなく、境界上でもない。 王が呪いを受けることなく出発地から目的地に辿り着けないときは `Impossible`と出力すること。 辿り着ける場合は王が出発してから目的地に到着するのに最短で何分かかるか出力すること。 小数点以下何桁でも出力してよく、絶対誤差・相対誤差の少なくとも片方が10-6以下であれば正答と見なされる。 ただし、呪いの範囲の境界上では呪いを受けることはない。 また、王が出発する時点でのいずれかの魔女の呪いの半径が $ Wi,r\ -\ 10-3 $ から $ Wi,r\ +\ 10-3 $ の範囲で変化しても呪いを受けずに目的地に辿り着けるかどうかは変わらない。 - $ -1000\ ≦\ Sx,\ Sy,\ Gx,\ Gy,\ Wi,x\ Wi,y\ ≦\ 1000 $ - $ (Sx,\ Sy)\ ≠\ (Gx,\ Gy) $ - $ 1\ ≦\ V\ ≦\ 100 $ - $ 1\ ≦\ N\ ≦\ 10 $ - $ 1\ ≦\ Wi,r\ ≦\ 1000 $ - $ 0\ ≦\ Wi,v\ ≦\ 100 $ この問題は(1)〜(4)の部分点に分かれていて、上で与えられた条件の他に以下を満たします。 - (1) 50点 : $ N\ =\ 1\ かつ\ Wi,v\ =\ 0 $ - (2) 100点 : $ Wi,v\ =\ 0 $ - (3) 100点 : $ Wi,v\ =\ 0\ または\ V\ i,v $ - (4) 150点 : $ N\ =\ 1\ かつ\ 0\ i,v $ ``` 0 0 10 10 2 1 5 5 5 0 ``` ``` 8.926990817 ``` ``` 0 0 10 10 2 2 4 6 4 0 6 4 4 0 ``` ``` 9.141592654 ``` ``` 0 0 10 10 2 2 4 6 4 0 6 4 4 3 ``` ``` Impossible ``` ``` 22 53 98 32 4 1 69 40 2 1 ``` ``` 21.425021992 ```

N/A

N/A