4580 . B5. 戰地記者與他的掃雷機 (Mine)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

相傳在遙遠的從前兼備電子與哀粒洗吸在其邊境發生了一場戰役，在點交一二間的高牆互相攻防，在此之外還有獨立的第三方勢力，稱為靴掌結，靴掌結在高牆下埋了若干顆 AaW / Snow 炸彈，如果有人在方圓十米內同時觸發 AaW 炸彈和 Snow 炸彈，便會被其放出來的 xxx 的能量閃瞎雙眼，從此失明。

現在兼備電子派出了一名戰地記者，這名戰地記者身懷風暴的力量，可以在大地上散播風暴軸，一旦一塊地被任三個風暴軸包圍，戰地記者便可透過敗家之眼觀測到這塊地中的 AaW / Snow 炸彈的數量及位置。

然而戰地記者隨身攜帶的風暴軸實在太少了，因此他決定發動風暴之力，同時將他所有的風暴軸以自己為中心旋轉數周，同時掃描這些風暴軸所覆蓋到的面積。

現在戰地記者所在的座標為$(0,0)$，給你 $N$ 個風暴軸的座標，請幫戰地記者計算他能掃描到多少土地範圍吧。

Input Format

$N$
$x_1\;\; y_1$
$...$
$x_N\;\; y_N$

第一行有一個正整數$N$代表共有幾個風暴軸
接下來$N$行分別為這$N$個風暴軸的座標

$N \le 100000$
$1 \le x_i,y_i \le 20000$
保證座標皆為正整數

Output Format

輸出一正實數 $A$ 代表戰地記者的風暴掃雷機能掃掠 $A\pi$ 的面積
若你的答案與標準答案絕對誤差在 $10 ^ {-6}$ 以內，就算正確。

Sample Input 1

3
2 2
4 3 
3 4

Sample Output 1

17

Sample Input 2

5
1 3
3 1
3 5
5 3
3 3

Sample Output 2

26

Sample Input 3

7
4 8
13 14
12 1
2 8
2 18
19 13
14 4

Sample Output 3

470.697986577181211

Hints

  • 範測 1 示意圖：

    範測 1 示意圖

  • 範測 2 示意圖：

    範測 2 示意圖

你們在上機考我在考會考
Problem Statement by cjtsai

Problem Source

TopCoder

AaW
學弟電爛我了

User's AC Ratio

66.7% (2/3)

Tags

學術上機考 112 學年度

Problem Setter

Created by AaW

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~12 $N < 20, 1 < x,\,y < 20$ 13
3 13~22 保證所有風暴軸的座標依序構成一個簡單凸多邊形 42
4 23~42 無其他限制 45

Testdata and Limits

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