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) Output Limit (KiB)
0 900 65536 262144
1 900 65536 262144
2 900 65536 262144
3 900 65536 262144
4 900 65536 262144
5 900 65536 262144
6 900 65536 262144
7 900 65536 262144
8 900 65536 262144
9 900 65536 262144
10 900 65536 262144
11 900 65536 262144
12 1400 65536 262144
13 1400 65536 262144
14 400 65536 262144
15 400 65536 262144
16 400 65536 262144