10 . 壅壅鹿鹿

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

50.0% (3/6)

Tags

ntucpc-challenge1

Description


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

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

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

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

Input Format

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

  • 1≤N≤5×104
  • −109≤xi,yi≤109
  • (xi,yi)≠(xj,yj),∀i≠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

第一筆範例測資中，有 18 的機率 3 個地點都被視為重要的，此時園區的範圍如下圖，面積為 1。除此之外，其餘的狀況園區的面積皆為 0，故期望值為 18=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≤300 1
3 0~42 N≤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