Universal Cup Judging System

Universal Cup

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

無限に広がるテーブルの上に、2 つの異なる点 $A = (A_x, A_y)$ と $B = (B_x, B_y)$ が与えられます。

また、それぞれが長さ $W$ の線分である $M$ 本の棒を持っています。これらの棒は、任意の位置および向きでテーブル上のどこにでも配置できます。棒同士が重なっても構いません。ただし、どの棒も点 $A$ や点 $B$ を含んではいけません。

1 匹のアリが $A$ から出発し、$B$ に到達しようとしています。アリはテーブル上のどこでも歩くことができますが、どの棒も横切ることはできません。

アリが $A$ から $B$ へ移動する最短経路の長さができるだけ大きくなるように棒を配置したいです。

アリを完全に塞いで $A$ から $B$ への経路が存在しないようにできる場合、答えは $-1$ です。

そうでない場合、すべての有効な棒の配置における $A$ から $B$ への最短経路の長さの上限(supremum)$^\dagger$ を $L$ とします。この値を達成する配置が存在する場合、$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.