Na nieskończonym stole dane są dwa różne punkty $A = (A_x, A_y)$ oraz $B = (B_x, B_y)$.
Masz również $M$ patyków, z których każdy jest odcinkiem o długości $W$. Możesz umieścić te patyki w dowolnym miejscu na stole, w dowolnej pozycji i orientacji. Patyki mogą się nakładać. Żaden patyk nie może jednak zawierać punktu $A$ ani punktu $B$.
Mrówka startuje w punkcie $A$ i chce dotrzeć do punktu $B$. Może chodzić po całym stole, ale nie może przekroczyć żadnego patyka.
Chcesz rozmieścić patyki tak, aby długość najkrótszej ścieżki mrówki z $A$ do $B$ była jak największa.
Jeśli można całkowicie zablokować mrówkę, tak że nie istnieje żadna ścieżka z $A$ do $B$, odpowiedzią jest $-1$.
W przeciwnym razie niech $L$ będzie kresem górnym (supremum)$^\dagger$ długości najkrótszych ścieżek z $A$ do $B$ po wszystkich poprawnych rozmieszczeniach patyków. Jeśli istnieje rozmieszczenie osiągające tę wartość, $L$ jest po prostu wartością maksymalną. Jeśli żadne pojedyncze rozmieszczenie jej nie osiąga, ale rozmieszczenia mogą się do niej dowolnie przybliżać, nadal musisz wypisać $L$.
$^\dagger$ Kres górny (najmniejsze ograniczenie górne) zbioru liczb rzeczywistych to najmniejsza liczba rzeczywista, która jest większa lub równa każdej wartości w tym zbiorze. Może on, ale nie musi, być osiągany przez pewną wartość ze zbioru.
Wejście
Wejście podane jest w następującym formacie:
T A_x A_y B_x B_y M W ...
- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $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$
- Gwarantuje się, że $(A_x, A_y) \ne (B_x, B_y)$.
Wyjście
Dla każdego przypadku testowego:
- Wypisz $-1$, jeśli mrówkę można całkowicie zablokować;
- W przeciwnym razie wypisz jedną liczbę rzeczywistą — zdefiniowaną powyżej wartość $L$.
Niech $X$ będzie poprawną odpowiedzią, a $Y$ Twoim wyjściem. Twoje wyjście zostanie uznane za poprawne wtedy i tylko wtedy, gdy $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.
Przykład
Wejście 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
Wyjście 1
-1 1425074478.231629371643066
Uwaga
Przypadek testowy 1: Można wykazać, że rozmieszczając patyki w sposób optymalny, da się całkowicie zablokować mrówkę.