在一個無限大的桌面上,給你兩個不同的點 $A = (A_x, A_y)$ 和 $B = (B_x, B_y)$。
你還有 $M$ 根木棍,每根木棍都是長度為 $W$ 的線段。你可以將這些木棍放置在桌面上的任何位置,具有任意的位置和方向。木棍可以重疊。然而,任何木棍都不能包含點 $A$ 或點 $B$。
一隻螞蟻從 $A$ 出發,想要到達 $B$。牠可以在桌面上的任何地方行走,但不能跨越任何木棍。
你想放置這些木棍,使得螞蟻從 $A$ 到 $B$ 的最短路徑長度盡可能大。
如果可以完全阻斷螞蟻,使得不存在從 $A$ 到 $B$ 的路徑,則答案為 $-1$。
否則,令 $L$ 為在所有合法的木棍放置方案中,從 $A$ 到 $B$ 的最短路徑長度的上確界(supremum)$^\dagger$。如果存在某種放置方案可以達到該值,則 $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:可以證明,透過最優地放置木棍,可以完全阻斷螞蟻。