På ett oändligt bord ges två skilda punkter $A = (A_x, A_y)$ och $B = (B_x, B_y)$.
Du har också $M$ pinnar, där varje pinne är ett linjesegment med längden $W$. Du får placera dessa pinnar var som helst på bordet, med valfri position och orientering. Pinnar får överlappa varandra. Ingen pinne får dock innehålla punkten $A$ eller punkten $B$.
En myra startar vid $A$ och vill nå $B$. Den får gå var som helst på bordet, förutom att den inte kan korsa någon pinne.
Du vill placera pinnarna så att längden på den kortaste vägen för myran från $A$ till $B$ blir så stor som möjligt.
Om det är möjligt att blockera myran helt så att ingen väg från $A$ till $B$ existerar, är svaret $-1$.
Annars, låt $L$ vara supremum$^\dagger$ av de kortaste väglängderna från $A$ till $B$ över alla giltiga placeringar av pinnarna. Om det finns en placering som uppnår detta värde är $L$ helt enkelt maximum. Om ingen enskild placering uppnår det, men placeringar kan komma godtyckligt nära, måste du ändå skriva ut $L$.
$^\dagger$ Supremum (minsta övre gräns) för en mängd reella tal är det minsta reella tal som är större än eller lika med varje värde i mängden. Det kan men behöver inte uppnås av ett värde i mängden.
Indata
Indata ges i följande format:
T A_x A_y B_x B_y M W ...
- Alla indatavärden är heltal.
- $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$
- Det garanteras att $(A_x, A_y) \ne (B_x, B_y)$.
Utdata
För varje testfall:
- Skriv ut $-1$ om myran kan blockeras helt;
- Annars, skriv ut ett enda reellt tal — värdet $L$ som definierats ovan.
Låt $X$ vara det korrekta svaret och $Y$ vara din utdata. Din utdata betraktas som korrekt om och endast om $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.
Exempel
Indata 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
Utdata 1
-1 1425074478.231629371643066
Förklaring
Testfall 1: Det kan visas att genom att placera pinnarna optimalt kan myran blockeras helt.