無限に広がるテーブルの上に、2 つの異なる点 $A = (A_x, A_y)$ と $B = (B_x, B_y)$ が与えられます。
また、それぞれが長さ $W$ の線分である $M$ 本の棒を持っています。これらの棒は、任意の位置および向きでテーブル上のどこにでも配置できます。棒同士が重なっても構いません。ただし、どの棒も点 $A$ や点 $B$ を含んではいけません。
1 匹のアリが $A$ から出発し、$B$ に到達しようとしています。アリはテーブル上のどこでも歩くことができますが、どの棒も横切ることはできません。
アリが $A$ から $B$ へ移動する最短経路の長さができるだけ大きくなるように棒を配置したいです。
アリを完全に塞いで $A$ から $B$ への経路が存在しないようにできる場合、答えは $-1$ です。
そうでない場合、すべての有効な棒の配置における $A$ から $B$ への最短経路の長さの上限(supremum)$^\dagger$ を $L$ とします。この値を達成する配置が存在する場合、$L$ は単なる最大値です。単一の配置では達成できないものの、限りなく近づけることができる場合でも、$L$ を出力しなければなりません。
$^\dagger$ 実数の集合の上限(最小上界)とは、その集合のすべての値以上である最小の実数のことです。集合内の値によって達成される場合もあれば、されない場合もあります。
入力
入力は以下の形式で与えられます:
T A_x A_y B_x B_y M W ...
- 入力値はすべて整数である。
- $1 \le T \le 10^4$
- $0 \le A_x, A_y, B_x, B_y \le 10^9$
- $1 \le M, W \le 10^9$
- $(A_x, A_y) \ne (B_x, B_y)$ が保証される。
出力
各テストケースについて:
- アリを完全に塞ぐことができる場合は $-1$ を出力せよ;
- そうでない場合は、上で定義された実数値 $L$ を出力せよ。
正しい答えを $X$、あなたの出力を $Y$ とする。$|Y - X| \le 10^-6 \cdot \max(1, |X|)$ を満たすとき、かつそのときに限り、出力は正解と判定される。
入出力例
入力例 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
出力例 1
-1 1425074478.231629371643066
注記
テストケース 1: 棒を最適に配置することで、アリを完全に塞ぐことができることが示せます。