Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

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.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.