喺一張無限大嘅枱上面,俾你兩個唔同嘅點 $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:可以證明,透過最優咁擺放木棍,可以完全封住隻螞蟻。