根據可靠消息指出,恐怖份子在Taike city中四週設置了許多炸彈。並計畫在過年前夕引爆。爆炸將會對城市造成無數的破壞,所以政府必須盡快做出所有能做的防範措施來降低潛在危險。
幸運的是,經過ASF小組(Army Special Forces)的調查,我們能夠清楚的知道炸彈的位置和影響範圍,我們將此範圍稱之為Red Area。Red Area是一個以炸彈為中心的圓形區域,給定有N個炸彈,第i個炸彈的位置在(xi,yi),它的Red Area半徑為ri。
Tauke city決定在所有Red Area的邊界上圍上封鎖線,現在你的工作就是去計算這些封鎖線的總長度。Red Area有可能互相重疊,形成不是圓形的範圍。也可能有數個獨立的安全區域,被Red Area包圍住,但是卻不會被炸彈波及到。
舉例來說,如圖1,城市中有兩顆炸彈,位置分別是 (0,0) 和 (2,0) ,它們的Red Area半徑都是2。因為兩炸彈的Red Area有互相重疊,所以可以被一條封鎖線包圍,封鎖線的總長度是16.76。再舉個例,如圖2,程式中有八顆炸彈,位置分別為 (1,1) , (1,3) , (1,5) , (3,1) , (3,5) , (5,1) , (5,3) 和 (5,5),它們的Red Area半徑為1,八顆炸彈的Red Area包圍出一個獨立的安全區域(用陰影部分表示),所以需要的封鎖線包括了內部和外部兩條,兩條線的長度合為50.27。
Hint:圓的周長 L = 2πr , π = 3.14159265 , r是圓的半徑。
1.炸彈的數量N是一個整數,且 1 <= N <= 100。
2.第i個炸彈的座標和半徑都是整數,且 -900 <= xi <= 900 、 -900 <= yi <= 900 、 0 < ri <= 20
3.每個炸彈的位置都不同,任兩個炸彈不會有同樣的座標。
2 2 0 0 2 2 0 2 8 1 1 1 1 3 1 1 5 1 3 1 1 5 1 1 5 3 1 3 5 1 5 5 1
1.68 1 5.03 1
Like to bet?
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|