Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

На бесконечном столе даны две различные точки $A = (A_x, A_y)$ и $B = (B_x, B_y)$.

У вас также есть $M$ палочек, каждая из которых представляет собой отрезок длины $W$. Вы можете размещать эти палочки где угодно на столе, в любом положении и под любым углом. Палочки могут перекрываться. Однако ни одна палочка не может содержать точку $A$ или точку $B$.

Муравей начинает движение из точки $A$ и хочет добраться до точки $B$. Он может ходить где угодно по столу, но не может пересекать ни одну палочку.

Вы хотите разместить палочки так, чтобы длина кратчайшего пути муравья из $A$ в $B$ была как можно больше.

Если можно полностью заблокировать муравья так, что пути из $A$ в $B$ не будет существовать, ответом является $-1$.

В противном случае пусть $L$ — точная верхняя грань (супремум)$^\dagger$ длин кратчайших путей из $A$ в $B$ по всем допустимым размещениям палочек. Если существует размещение, на котором достигается это значение, то $L$ — это просто максимум. Если ни одно конкретное размещение его не достигает, но размещения могут приближаться к нему сколь угодно близко, вы всё равно должны вывести $L$.

$^\dagger$ Точная верхняя грань (наименьшая верхняя граница) множества вещественных чисел — это наименьшее вещественное число, которое больше или равно каждому значению в множестве. Она может как достигаться, так и не достигаться на некотором элементе множества.

Входные данные

Входные данные даны в следующем формате:

T
A_x A_y B_x B_y M W
...
  • Все входные значения являются целыми числами.
  • $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$
  • Гарантируется, что $(A_x, A_y) \ne (B_x, B_y)$.

Выходные данные

Для каждого набора входных данных:

  • Выведите $-1$, если муравья можно полностью заблокировать;
  • В противном случае выведите одно вещественное число — определённое выше значение $L$.

Пусть $X$ — правильный ответ, а $Y$ — ваш вывод. Ваш вывод считается правильным тогда и только тогда, когда $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.

Пример

Входные данные 1

2
0 0 1 1 343 434
4 5 786331192 707731892 1 639711202

Выходные данные 1

-1
1425074478.231629371643066

Примечание

Тестовый пример 1: Можно показать, что при оптимальном размещении палочек муравья можно полностью заблокировать.

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.