Universal Cup Judging System

Universal Cup

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

在一個無限大的桌面上,給你兩個不同的點 $A = (A_x, A_y)$ 和 $B = (B_x, B_y)$。

你還有 $M$ 根木棍,每根木棍都是長度為 $W$ 的線段。你可以將這些木棍放置在桌面上的任何位置,具有任意的位置和方向。木棍可以重疊。然而,任何木棍都不能包含點 $A$ 或點 $B$。

一隻螞蟻從 $A$ 出發,想要到達 $B$。牠可以在桌面上的任何地方行走,但不能跨越任何木棍。

你想放置這些木棍,使得螞蟻從 $A$ 到 $B$ 的最短路徑長度盡可能大。

如果可以完全阻斷螞蟻,使得不存在從 $A$ 到 $B$ 的路徑,則答案為 $-1$。

否則,令 $L$ 為在所有合法的木棍放置方案中,從 $A$ 到 $B$ 的最短路徑長度的上確界(supremum)$^\dagger$。如果存在某種放置方案可以達到該值,則 $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.