Universal Cup Judging System

Universal Cup

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

Trên một mặt bàn vô hạn, bạn được cho hai điểm phân biệt $A = (A_x, A_y)$ và $B = (B_x, B_y)$.

Bạn cũng có $M$ chiếc que, mỗi chiếc là một đoạn thẳng có độ dài $W$. Bạn có thể đặt những chiếc que này ở bất kỳ đâu trên bàn, với vị trí và hướng tùy ý. Các chiếc que được phép chồng lên nhau. Tuy nhiên, không chiếc que nào được chứa điểm $A$ hoặc điểm $B$.

Một con kiến xuất phát từ $A$ và muốn đi đến $B$. Nó có thể bò ở bất kỳ đâu trên bàn, ngoại trừ việc không thể băng qua bất kỳ chiếc que nào.

Bạn muốn đặt các chiếc que sao cho độ dài đường đi ngắn nhất của con kiến từ $A$ đến $B$ là lớn nhất có thể.

Nếu có thể chặn hoàn toàn con kiến sao cho không tồn tại đường đi từ $A$ đến $B$, câu trả lời là $-1$.

Ngược lại, gọi $L$ là cận trên đúng (supremum)$^\dagger$ của độ dài đường đi ngắn nhất từ $A$ đến $B$ trên tất cả các cách đặt que hợp lệ. Nếu có một cách đặt đạt được giá trị này, $L$ đơn giản là giá trị lớn nhất. Nếu không có cách đặt đơn lẻ nào đạt được nó, nhưng có thể tiến sát tùy ý, bạn vẫn phải in ra $L$.

$^\dagger$ Cận trên đúng (cận trên nhỏ nhất) của một tập hợp các số thực là số thực nhỏ nhất lớn hơn hoặc bằng mọi giá trị trong tập hợp đó. Nó có thể đạt được hoặc không đạt được bởi một giá trị trong tập hợp.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

T
A_x A_y B_x B_y M W
...
  • Tất cả các giá trị đầu vào đều là số nguyên.
  • $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$
  • Đảm bảo rằng $(A_x, A_y) \ne (B_x, B_y)$.

Dữ liệu ra

Với mỗi bộ test:

  • In ra $-1$ nếu có thể chặn hoàn toàn con kiến;
  • Ngược lại, in ra một số thực duy nhất — giá trị $L$ được định nghĩa ở trên.

Gọi $X$ là đáp án đúng và $Y$ là kết quả của bạn. Kết quả của bạn được coi là đúng khi và chỉ khi $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

-1
1425074478.231629371643066

Giải thích

Test case 1: Có thể chứng minh rằng bằng cách đặt các chiếc que một cách tối ưu, con kiến có thể bị chặn hoàn toàn.

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.