Auf einem unendlichen Tisch sind zwei verschiedene Punkte $A = (A_x, A_y)$ und $B = (B_x, B_y)$ gegeben.
Außerdem hast du $M$ Stöcke, von denen jeder eine Strecke der Länge $W$ ist. Du darfst diese Stöcke überall auf dem Tisch in beliebiger Position und Ausrichtung platzieren. Stöcke dürfen sich überlappen. Allerdings darf kein Stock den Punkt $A$ oder den Punkt $B$ enthalten.
Eine Ameise startet bei $A$ und möchte $B$ erreichen. Sie kann überall auf dem Tisch laufen, darf jedoch keinen Stock überqueren.
Du möchtest die Stöcke so platzieren, dass die Länge des kürzesten Weges für die Ameise von $A$ nach $B$ so groß wie möglich ist.
Wenn es möglich ist, die Ameise vollständig zu blockieren, sodass kein Weg von $A$ nach $B$ existiert, lautet die Antwort $-1$.
Andernfalls sei $L$ das Supremum$^\dagger$ der Längen der kürzesten Wege von $A$ nach $B$ über alle gültigen Platzierungen der Stöcke. Wenn es eine Platzierung gibt, die diesen Wert erreicht, ist $L$ einfach das Maximum. Wenn keine einzelne Platzierung ihn erreicht, aber Platzierungen ihm beliebig nahe kommen können, musst du dennoch $L$ ausgeben.
$^\dagger$ Das Supremum (kleinste obere Schranke) einer Menge reeller Zahlen ist die kleinste reelle Zahl, die größer oder gleich jedem Wert in der Menge ist. Es kann von einem Wert in der Menge angenommen werden oder auch nicht.
Eingabe
Die Eingabe erfolgt im folgenden Format:
T A_x A_y B_x B_y M W ...
- Alle Eingabewerte sind ganze Zahlen.
- $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$
- Es wird garantiert, dass $(A_x, A_y) \ne (B_x, B_y)$ gilt.
Ausgabe
Für jeden Testfall:
- Gib $-1$ aus, wenn die Ameise vollständig blockiert werden kann;
- Gib andernfalls eine einzelne reelle Zahl aus — den oben definierten Wert $L$.
Sei $X$ die richtige Antwort und $Y$ deine Ausgabe. Deine Ausgabe gilt genau dann als richtig, wenn $|Y - X| \le 10^-6 \cdot \max(1, |X|)$ gilt.
Beispiel
Eingabe 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
Ausgabe 1
-1 1425074478.231629371643066
Hinweis
Testfall 1: Es lässt sich zeigen, dass die Ameise durch optimales Platzieren der Stöcke vollständig blockiert werden kann.