科科男素有東京死神之稱,想不到最近業績更是蒸蒸日上,在春酒晚宴上,吃飯吃到一半突然聞到一股杏仁味,緊接著周遭有 $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$。
第一列有一個正整數$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 |
若封鎖線的總長度使用科學記號表示為$a\times 10^ b$的形式,其中$1\leq a<10$,請輸出$a$和$b$(以空格隔開)。
你的答案$P$只要與標準答案$Q$相對誤差在$10^ {-3}$以內(也就是$\frac{|P-Q|}{Q}\leq 10^ {-3}$)就會被視為正確。
在#include <math.h>
之後,你可以使用acos(-1)
來獲取$\pi$的值。
建國中學105學年度校隊補選pB
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 13 |
2 | 0~10 | 35 |
3 | 0~13 | 52 |
4 | 0~16 | 50 |