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.