下落的圆盘
Time Limit: 10 Sec Memory Limit: 162 MB[][][]Description
有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。
看下面这副图, 所有的红色线条的总长度即为所求。
Input
第一行为1个整数n
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.Output
最后的周长，保留三位小数
Sample Input
2 1 0 0 1 1 0
Sample Output
10.472
HINT
n <= 1000
Solution
显然是一道计算几何题。
考虑一个圆对于答案的贡献，显然是这个圆的周长 - 后面的圆把它覆盖掉的周长的并。那么我们就考虑怎么求这个并。
先考虑怎样记录下一个答案，显然直接扣掉单个圆对它的覆盖是不可行的，要减去重叠的情况。
既然边不可行，我们就用角度。显然，若我们求出 两圆交点的角度 即可解决这题。
我们考虑求圆A被圆B覆盖的角度：现在我们有两个圆的半径、圆心距。我们就可以得到 圆A与圆B的圆心连线 与 圆A半径 的夹角。
我们也可以知道 圆A与圆B的圆心连线 与 x轴的夹角。
这样的话，就可以把单个圆对于它的贡献记录到栈里面，最后扫一遍求一下剩余的角度，乘上R就是它对于答案的贡献了。
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std; 10 typedef unsigned long long s64;11 12 const int ONE = 1000005;13 const double pi = acos(-1.0);14 15 int n;16 struct power17 {18 double x, y, r;19 }a[ONE];20 21 struct circle22 {23 double a, b;24 }stk[ONE];25 int top;26 27 double Ans;28 29 bool cmp(const circle &a, const circle &b)30 {31 if(a.a != b.a) return a.a < b.a;32 return a.b < b.b;33 }34 35 int get()36 { 37 int res,Q=1; char c;38 while( (c=getchar())<48 || c>57)39 if(c=='-')Q=-1;40 if(Q) res=c-48; 41 while((c=getchar())>=48 && c<=57) 42 res=res*10+c-48; 43 return res*Q; 44 }45 46 double sqr(double x) { return x * x;}47 double dist(power a, power b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}48 49 double Calc(power a, power b)50 {51 double A = a.r, B = b.r, C = dist(a, b);52 double cosB = (sqr(A) + sqr(C) - sqr(B)) / (2 * A * C);53 double angle = atan2(a.x - b.x, a.y - b.y), add = acos(cosB);54 stk[++top] = (circle){angle - add, angle + add};55 }56 57 double init(power a, power b) { return a.r + dist(a, b) <= b.r;}58 double sect(power a, power b) { return fabs(a.r - b.r) < dist(a, b) && dist(a, b) < a.r + b.r;}59 60 double Deal(int id)61 {62 top = 0;63 for(int i = id+1; i <= n; i++)64 if(init(a[id], a[i])) return 0;65 66 for(int i = id+1; i <= n; i++)67 if(sect(a[id], a[i])) Calc(a[id], a[i]);68 69 for(int i = 1; i <= top; i++)70 {71 while(stk[i].a < 0) stk[i].a += 2 * pi;72 while(stk[i].b < 0) stk[i].b += 2 * pi;73 if(stk[i].a > stk[i].b) stk[++top] = (circle){ 0, stk[i].b}, stk[i].b = 2*pi;74 }75 76 sort(stk + 1, stk + top + 1, cmp);77 double last = 0.0, sum = 0.0;78 for(int i = 1; i <= top; i++)79 if(stk[i].a > last) sum += stk[i].a - last, last = stk[i].b;80 else last = max(last, stk[i].b);81 82 sum += 2 * pi - last;83 return a[id].r * sum;84 }85 86 int main()87 {88 n = get();89 for(int i = 1; i <= n; i++)90 scanf("%lf %lf %lf", &a[i].r, &a[i].x, &a[i].y);91 for(int i = 1; i <= n; i++)92 Ans += Deal(i);93 printf("%.3lf", Ans);94 }