121 . 鄉村大道

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

0.0% (0/1)

Submission's AC Ratio

0.0% (0/1)

Tags

ioicamp ioicamp-2023

Description

小 Y 和小 P 是在 G 社上班的員工，一天他們跟公司請假到鄉村去玩耍，鄉村十分愜意，遠遠望去只有一望無際的草原，一些在草原上的大樹以及一條非常筆直的道路。這時小 Y 突然有一個有趣的主意，他帶著公司最新研發的手機想要測試拍照功能，小 P 建議小 Y 可以測試看看廣角鏡頭的功能。

具體來說，可以將一望無際的草原想像成一個座標平面，大樹可以比擬成座標平面上的 $N$ 個點，道路為平面上的一條直線，而小 Y 與小 P 均站在這條道路上，並且為了保持交通安全，所以所有樹都不落在道路上。為了展現廣角鏡頭的功能，小 Y 與小 P 想要在道路上選定一個點並使用廣角鏡頭功能將所有樹都拍進照片內，手機的拍照範圍可以想像成一個以該手機為圓心半徑長為無限大的扇形，扇形角度根據手機廣角角度設定而定。小 Y 與小 P 想將其廣角功能展現的淋漓盡致，所以他們想要在把角度開到恰好能容納所有大樹的同時，這個角度也要盡量大。請你幫小 Y 與小 P 選定一個拍攝位置能夠滿足他們的需求，另外，因為廣角鏡頭只能支援最多 $180^ {\circ}$，所以請避免選擇一個無法容納所有大樹的位置。

Input Format

輸入第一行包含五個整數 $N, u_1, v_1, u_2, v_2$ 以一個空白分隔，代表平面上一共有 $N$ 棵樹，並且小 Y 與小 P 分別站在座標 $(u_1, v_1)$ 及 $(u_2, v_2)$ 上。

接下來有 $N$ 行，第 $i$ 行有兩個以空白分隔的整數 $x_i, y_i$，代表第 $i$ 棵樹在平面上的座標。

  • $2 \leq N \leq 10^ 5$
  • $-10^ 6 \leq u_1, v_1, u_2, v_2, x_i, y_i \leq 10^ 6$
  • $(u_1, v_1) \neq (u_2, v_2)$
  • 所有樹的位置都不相同，亦即 $(x_i, y_i) \neq (x_j, y_j)$
  • 輸入保證所有樹都不會在道路上

Output Format

請輸出最大可能需要設定的廣角餘弦值，亦即若角度為 $x$ 則請輸出 $\cos(x)$。

參賽者的答案會被視為正確如果參賽者輸出與評測答案誤差小於 $10^ {-6}$。

Sample Input 1

3 1 0 2 1
0 0
-1 1
1 2

Sample Output 1

-0.055641755904

Sample Input 2

3 0 0 1 -1
1 1
-1 0
0 -1

Sample Output 2

-1

Sample Input 3

5 17 2 -19 10
3 5
-4 -3
1 1
0 0
-1 2

Sample Output 3

-0.413808580253

Hints

Problem Source

IOICamp 2023 Day4 pD

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~39 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 65536 1 2
1 4000 524288 65536 1 2
2 4000 524288 65536 1 2
3 4000 524288 65536 2
4 4000 524288 65536 2
5 4000 524288 65536 2
6 4000 524288 65536 2
7 4000 524288 65536 2
8 4000 524288 65536 2
9 4000 524288 65536 2
10 4000 524288 65536 2
11 4000 524288 65536 2
12 4000 524288 65536 2
13 4000 524288 65536 2
14 4000 524288 65536 2
15 4000 524288 65536 2
16 4000 524288 65536 2
17 4000 524288 65536 2
18 4000 524288 65536 2
19 4000 524288 65536 2
20 4000 524288 65536 2
21 4000 524288 65536 2
22 4000 524288 65536 2
23 4000 524288 65536 2
24 4000 524288 65536 2
25 4000 524288 65536 2
26 4000 524288 65536 2
27 4000 524288 65536 2
28 4000 524288 65536 2
29 4000 524288 65536 2
30 4000 524288 65536 2
31 4000 524288 65536 2
32 4000 524288 65536 2
33 4000 524288 65536 2
34 4000 524288 65536 2
35 4000 524288 65536 2
36 4000 524288 65536 2
37 4000 524288 65536 2
38 4000 524288 65536 2
39 4000 524288 65536 2
Submit
Back to Top