TopCoder

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

User's AC Ratio

50.0% (2/4)

Submission's AC Ratio

8.0% (2/25)

Tags

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 1

2
0 0 2
2 0 2

Sample Output 1

1.6755 1

Sample Input 2

4
0 0 1
2 0 1
0 2 1
2 2 1

Sample Output 2

2.5133 1

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0~4 13
2 0~10 35
3 0~13 52
4 0~16 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1 2 3 4
1 900 65536 262144 1 2 3 4
2 900 65536 262144 1 2 3 4
3 900 65536 262144 1 2 3 4
4 900 65536 262144 1 2 3 4
5 900 65536 262144 2 3 4
6 900 65536 262144 2 3 4
7 900 65536 262144 2 3 4
8 900 65536 262144 2 3 4
9 900 65536 262144 2 3 4
10 900 65536 262144 2 3 4
11 900 65536 262144 3 4
12 1400 65536 262144 3 4
13 1400 65536 262144 3 4
14 400 65536 262144 4
15 400 65536 262144 4
16 400 65536 262144 4