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.