TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

4.2% (1/24)

Description

科科男素有東京死神之稱,想不到最近業績更是蒸蒸日上,在春酒晚宴上,吃飯吃到一半突然聞到一股杏仁味,緊接著周遭有 $N$ 個人倒下。

為了避免現場跡證遭到污染,必須立刻保護每個受害著周圍的區塊,經過科科男的調查與紀錄,我們已經知道 $N$ 位受害者的所在位置,第 $i$ 位受害者的位置用 $(X_i,Y_i)$ 表示,另外根據每位倒下的受害者體型以及隨身物品散落情形,第 $i$ 位受害者的周圍半徑 $r_i$ 的圓形區域內都應該封鎖管制,不能讓人隨便進入。

現在要在所有封鎖管制區的邊界圍上封鎖線,為了通知警方必須攜帶多少捆的封鎖線,請你計算封鎖線的總長度。

封鎖管制區有可能會互相重疊,形成不是圓形的範圍:
例如兩位受害者位置分別在(0,0)和(2,0),兩者封鎖管制區半徑皆為2,則封鎖管制區可以用一條長度$\frac{16 \pi}{3}$的封鎖線圍住。
又例如四位受害者位置分別在(0,0), (2,2), (2,0), (0,2),四個封鎖管制區半徑皆為1,則封鎖管制區需要外部和內部兩條封鎖線,兩條線的長度和為$8\pi$。

Input Format

第一列有一個正整數$N$代表受害者數量。
接下來$N$行,每行有三個整數$X_i, Y_i, r_i$,代表受害者所在位置為$(X_i,Y_i)$且封鎖半徑為$r_i$。

對於所有測資,$N \leq 3000; -900\leq X_i , Y_i \leq 900; 1\leq r_i \leq 20$。

子任務(測資) 額外限制 分數
1(0~4)$N \leq 2$13
2(0~10)$N \leq 30$35
3(0~13)$N \leq 100$52
3(0~16)無限制50

Output Format

若封鎖線的總長度使用科學記號表示為$a\times 10^ b$的形式,其中$1\leq a<10$,請輸出$a$和$b$(以空格隔開)。
你的答案$P$只要與標準答案$Q$相對誤差在$10^ {-3}$以內(也就是$\frac{|P-Q|}{Q}\leq 10^ {-3}$)就會被視為正確。

Sample Input

#Sample Input 1
2
0 0 2
2 0 2

#Sample Input 2
4
0 0 1
2 0 1
0 2 1
2 2 1

Sample Output

#Sample Output 1
1.6755 1

#Sample Output 2
2.5133 1

Hints

#include <math.h>之後,你可以使用acos(-1)來獲取$\pi$的值。

Problem Source

建國中學105學年度校隊補選pB

Subtasks

For Testdata: 0 ~ 4, Score: 13
For Testdata: 0 ~ 10, Score: 35
For Testdata: 0 ~ 13, Score: 52
For Testdata: 0 ~ 16, Score: 50
No. Time Limit (ms) Memory Limit (KiB)
0 900 65536
1 900 65536
2 900 65536
3 900 65536
4 900 65536
5 900 65536
6 900 65536
7 900 65536
8 900 65536
9 900 65536
10 900 65536
11 900 65536
12 1400 65536
13 1400 65536
14 400 65536
15 400 65536
16 400 65536