Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

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ę.

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.