[ZJ][蒙地卡羅模擬法] a648. A - Red Areas
內容 ：
根據可靠消息指出，恐怖份子在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?
出處
：
幾何無力的情況下，如何寫這種題目？
不求交點的話，切割一個圓為 n 等份，然後檢查端點是否在另一個圓中，
如果不存在於任何一個圓中 ans += (360/n) * pi/180 * r;
此時 n 越大越好，就跟積分差不多
/* Problem: a648 "A - Red Areas" from 陳伶志, PTC 2008 TOI2013 練習題 */
/* Language: CPP (1373 Bytes)
/* Result: AC(686ms, 325KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-03-29 09:12:47 */
/*****************************************************************/
#include <stdio.h>
#include <math.h>
const double pi = acos(-1);
int main() {
int t, n, i, j, k;
double xi[105], yi[105], ri[105];
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%lf %lf %lf", &xi[i], &yi[i], &ri[i]);
double ans = 0;
double theta, x, y;
int chbuf[105], m;
for(i = 0; i < n; i++) {
m = 0;
for(j = 0; j < n; j++) {
if(i == j) continue;
if(pow(xi[i]-xi[j], 2)+pow(yi[i]-yi[j], 2) < pow(ri[i]+ri[j], 2))
chbuf[m++] = j;
}
#define pp 10000
double ll = 0;
int flag = 1, cnt = 0;
for(j = 0; j < pp; j++) {
theta = 360.0*j*pi/180/pp;
x = ri[i]*cos(theta) + xi[i];
y = ri[i]*sin(theta) + yi[i];
for(k = 0; k < m; k++) {
if(pow(x-xi[chbuf[k]], 2)+pow(y-yi[chbuf[k]], 2) < ri[chbuf[k]]*ri[chbuf[k]])
break;
}
if(k == m)
cnt++;
}
ans += 2*pi*ri[i]*cnt/pp;
}
double a = log10(ans), b;
b = floor(a);
a = a-b;
printf("%.2lf %d\n", pow(10, a), (int)b);
}
return 0;
}