TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

50.0% (2/4)

Submission's AC Ratio

8.0% (2/25)

Tags

Description

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

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

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

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

Input Format

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

對於所有測資,N3000;900Xi,Yi900;1ri20

子任務(測資) 額外限制 分數
1(0~4)N213
2(0~10)N3035
3(0~13)N10052
3(0~16)無限制50

Output Format

若封鎖線的總長度使用科學記號表示為a×10b的形式,其中1a<10,請輸出ab(以空格隔開)。
你的答案P只要與標準答案Q相對誤差在103以內(也就是|PQ|Q103)就會被視為正確。

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)來獲取π的值。

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