a648. A - Red Areas
Tags :
Accepted rate : 46人/53人 ( 87% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-03-27 21:01

Content

根據可靠消息指出,恐怖份子在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.每個炸彈的位置都不同,任兩個炸彈不會有同樣的座標。 


Input
input的第一行有一個正整數表示接下來有幾組測資。每組測資的第一行有一個正整數N,表示這組測資有幾顆炸彈。接下來的N行,每行都有三個由空格分開的整數,xi , yi , 和 ri , ,表示了第i個炸彈的座標和Red Area的半徑。
Output
請印出兩個數字,由一個空格隔開。第一個數字a是一個實數, 0 < a < 10 。第二個數字是一個非負整數。而封鎖線的總長度為用科學符號表示的a×10b。注意,a需印出小數後兩位。
Sample Input #1
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 
Sample Output #1
1.68 1
5.03 1 
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 5.0s , <1K
公開 測資點#1 (10%): 5.0s , <1K
公開 測資點#2 (25%): 5.0s , <1M
公開 測資點#3 (25%): 5.0s , <1M
公開 測資點#4 (30%): 5.0s , <1M
Hint :

Like to bet?

 

Tags:
出處:
2013TOI陳伶志PTC 2008 [管理者: stanley17112 ... (Stanley) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」