三角函数计算+区间合并
对于每一个圆，判断接下来掉落的圆是否会覆盖它，用余弦定理之类的三角函数搞一搞就好了。计算出被覆盖的角的区间，然后并一下。
#include<cstdio> #include<cmath> #include<algorithm> #define N 1005 using namespace std; struct circle { double r, x, y; }c[N]; struct interval { double l, r; }inter[N<<1]; const double eps = 1e-7, pi = acos(-1.0); int icnt; bool cmp(interval a, interval b){return a.l<b.l||(a.l==b.l&&a.r>b.r);} void solve(circle a, circle b) { double dis=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); if(dis>=a.r+b.r+eps)return; if(dis<=b.r-a.r+eps) { inter[++icnt]=(interval){-pi,pi}; return; } if(dis<=a.r-b.r+eps) return; double angle = atan2(b.y-a.y,b.x-a.x); double angle2 = acos( (dis*dis+a.r*a.r-b.r*b.r)/(2*a.r*dis) ); double la = angle-angle2, ra = angle+angle2; if(la<-pi) { inter[++icnt]=(interval){la+2*pi,pi}; inter[++icnt]=(interval){-pi,ra}; } else if(ra>pi) { inter[++icnt]=(interval){la,pi}; inter[++icnt]=(interval){-pi,ra-2*pi}; } else inter[++icnt]=(interval){la,ra}; } int main() { int n; double ans=0; scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%lf%lf%lf",&c[i].r,&c[i].x,&c[i].y); for(int i = 1; i <= n; i++) { icnt=0; for(int j = i+1; j <= n; j++) solve(c[i],c[j]); sort(inter+1,inter+1+icnt,cmp); double lost=0, left=inter[1].l, right=inter[1].r; for(int j = 2; j <= icnt; j++) { if(inter[j].l>left) { if(inter[j].l>right) { lost+=right-left; left=inter[j].l; right=inter[j].r; } else if(right<inter[j].r)right=inter[j].r; } } if(icnt)lost+=right-left; if(lost<2*pi)ans+=c[i].r*(2*pi-lost); } printf("%.3lf",ans); return 0; }