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.