这道题题目很短,看一下数据范围n<1000,直接枚举圆盘。
对于圆盘i,枚举它上面的圆盘,计算圆盘i被它们覆盖的弧的起始位置与终止位置,然后线段覆盖可得圆盘i被覆盖的周长,就可得答案。
注意圆外离与内含的情况。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define pi 3.1415926535897932384626433832795 using namespace std; struct circle{double r,x,y;}a[10000]; struct arc{double a,b;}q[10000]; int n,le;double Ans; double di(circle a,circle b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double ang(double R,double d,double r) { return acos((R*R+d*d-r*r)/(2*R*d)); } bool cmp(arc a,arc b) { if (a.a==b.a)return a.b<b.b; else return a.a<b.a; } void add(double l,double r) { q[++le].a=l,q[le].b=r; } int main() { freopen("disc.in","r",stdin); freopen("disc.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i].r,&a[i].x,&a[i].y); for (int i=1;i<=n;i++) { bool f=0;le=0; for (int j=i+1;j<=n;j++) { double dis=di(a[i],a[j]); if (dis<=a[j].r-a[i].r) {f=1;break;} if (dis>=a[i].r+a[j].r||dis<=a[i].r-a[j].r) continue; double x=a[j].x-a[i].x,y=a[j].y-a[i].y; double a1=atan2(x,y)+pi; double a2=ang(a[i].r,dis,a[j].r); if (a1-a2<0) add(0,a1+a2), add(a1-a2+2*pi,2*pi);else if (a1+a2>2*pi) add(a1-a2,pi*2),add(0,a1+a2-2*pi); else add(a1-a2,a1+a2); } if (f==1)continue; sort(q+1,q+le+1,cmp); double l=-1,r=-1,sum=0; for (int j=1;j<=le;j++) if (q[j].a<=r) r=max(r,q[j].b); else { sum+=r-l; l=q[j].a; r=q[j].b; } sum+=r-l; Ans+=(2*pi-sum)*a[i].r; } printf("%.3f\n",Ans); return 0; }