10 . 壅壅鹿鹿

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

40.0% (2/5)

Tags

ntucpc-challenge1

Description


鹿乃子乃子平常會在日野動物園內打工

由於日野動物園內飼養的鹿數量逐漸增加，鹿隻經常會從園區逃離導致交通壅塞，園方打算重新安排鹿的展區。

園方記錄了鹿群經常出沒的 $N$ 個地點，其中第 $i$ 個地點的座標為 $(x_i, y_i)$。他們打算選擇其中的最重要的一些地點，並將園區範圍重新規劃成能納入這些地點的最小凸多邊形範圍。

不過由於詳細的觀測資料不小心跟虎視虎子的詩歌筆記一起燒毀了，他們沒辦法得知這 $N$ 個地點的鹿群數量及出沒頻率等重要資訊。最後他們決定，每一個地點都有獨立的 $50\%$ 的機率會被視為重要的。為了提早規劃園區的草地種植面積，請你寫一支程式幫他們算一算，在這樣的決定方式下，園區範圍的面積期望值是多少。

Input Format

輸入的第一行為一整數 $N$。接下來 $N$ 行，每行包含兩個整數 $x_i, y_i$，表示第 $i$ 個地點的座標。

  • $1 \le N \le 5 \times 10^ 4$
  • $-10^ 9 \le x_i,y_i \le 10^ 9$
  • $(x_i, y_i) \ne (x_j, y_j), \forall i \ne j$
  • 保證對於任意三個相異的點皆不共線

Output Format

輸出一個實數，表示園區範圍的面積期望值。

你輸出的實數與正確答案的相對或絕對誤差不超過 $10^ {-6}$ 皆會被視為正確。

Sample Input 1

3
0 0
2 0
0 1

Sample Output 1

0.125

Sample Input 2

6
0 0
5 -1
9 6
3 0
4 2
3 1

Sample Output 2

5.4140625

Sample Input 3

10
44 8
35 12
-46 -27
16 -17
-13 0
-36 -10
-37 -13
-36 10
35 18
-23 -39

Sample Output 3

1485.140625

Hints

第一筆範例測資中，有 $\frac18$ 的機率 $3$ 個地點都被視為重要的，此時園區的範圍如下圖，面積為 $1$。除此之外，其餘的狀況園區的面積皆為 $0$，故期望值為 $\frac18 = 0.125$。

注意到當沒有地點被視為重要的時，園區的面積為 $0$。

第二筆範例測資中，當 $6$ 個地點都被視為重要的時，園區的範圍如下圖，面積為 $19.5$。

image

Problem Source

改編自 YTP 2024 高中組程式挑戰營 p14 - 凸包面積

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~22 $N \leq 300$ 1
3 0~42 $N \leq 1500$ 9
4 0~52 無額外限制 90

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2 3 4
1 3000 524288 65536 1 2 3 4
2 3000 524288 65536 1 2 3 4
3 3000 524288 65536 2 3 4
4 3000 524288 65536 2 3 4
5 3000 524288 65536 2 3 4
6 3000 524288 65536 2 3 4
7 3000 524288 65536 2 3 4
8 3000 524288 65536 2 3 4
9 3000 524288 65536 2 3 4
10 3000 524288 65536 2 3 4
11 3000 524288 65536 2 3 4
12 3000 524288 65536 2 3 4
13 3000 524288 65536 2 3 4
14 3000 524288 65536 2 3 4
15 3000 524288 65536 2 3 4
16 3000 524288 65536 2 3 4
17 3000 524288 65536 2 3 4
18 3000 524288 65536 2 3 4
19 3000 524288 65536 2 3 4
20 3000 524288 65536 2 3 4
21 3000 524288 65536 2 3 4
22 3000 524288 65536 2 3 4
23 3000 524288 65536 3 4
24 3000 524288 65536 3 4
25 3000 524288 65536 3 4
26 3000 524288 65536 3 4
27 3000 524288 65536 3 4
28 3000 524288 65536 3 4
29 3000 524288 65536 3 4
30 3000 524288 65536 3 4
31 3000 524288 65536 3 4
32 3000 524288 65536 3 4
33 3000 524288 65536 3 4
34 3000 524288 65536 3 4
35 3000 524288 65536 3 4
36 3000 524288 65536 3 4
37 3000 524288 65536 3 4
38 3000 524288 65536 3 4
39 3000 524288 65536 3 4
40 3000 524288 65536 3 4
41 3000 524288 65536 3 4
42 3000 524288 65536 3 4
43 3000 524288 65536 4
44 3000 524288 65536 4
45 3000 524288 65536 4
46 3000 524288 65536 4
47 3000 524288 65536 4
48 3000 524288 65536 4
49 3000 524288 65536 4
50 3000 524288 65536 4
51 3000 524288 65536 4
52 3000 524288 65536 4
Submit
Back to Top