有 n 个圆盘从天而降，后面落下的可以盖住前面的。最后按掉下的顺序,在平面上依次测得每个圆盘的圆心和半径,问下落完成后从上往下看,整个图形的周长是多少,即你可以看到的圆盘的轮廓的圆盘的轮廓总长.例如下图的黑色线条的总长度即为所求。
【输入格式】
第一行为1个整数n
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.
【输出格式】
仅一个实数，表示所求的总周长,答案保留3位小数.
【样例输入】
2
1 0 0
1 1 0
【样例输出】
10.472
【提示】
30%的数据,n<=10
100%的数据,n<=1000
数学问题 计算几何
用余弦定理和三角函数可以计算出两圆相交部分的弧长。
对于每个圆，计算它和在它之后落下的所有圆的角。记录相交部分的弧对应的圆心角范围。将“圆心角”区间离散到0~2pi的数轴上，做线段覆盖。
知道了未被覆盖的角总共有多大，就能算出该圆未被覆盖的弧有多长。
注意如果求出的覆盖部分圆心角范围超出了0~2pi，要变换到0~2pi范围内
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-;
const int mxn=;
struct point{
double x,y;
point operator + (point b){return (point){x+b.x,y+b.y};}
point operator - (point b){return (point){x-b.x,y-b.y};}
double operator * (point b){return x*b.x+y*b.y;}
};
inline double Cross(point a,point b){
return a.x*b.y-a.y*b.x;
}
inline double dist(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double Len(point a){return sqrt(a*a);}
struct cir{
double x,y;
double r;
point operator + (cir b){return (point){x+b.x,y+b.y};}
point operator - (cir b){return (point){x-b.x,y-b.y};}
}c[mxn];
inline bool cover(cir a,cir b){
return (a.r>=b.r+Len(a-b));
}
struct line{
double l,r;
bool operator < (line b)const{
return (l<b.l)|| (l==b.l && r<b.r);
}
};
line CX(cir a,cir b){
double dis=Len(b-a);
double angle=acos((a.r*a.r+dis*dis-b.r*b.r)/(*a.r*dis));
double deg=atan2(a.x-b.x,a.y-b.y);//统一旋转pi角度,保证在-2pi~2pi范围内
return (line){deg-angle,deg+angle};
/* double t=(a.r*a.r+dis*dis-b.r*b.r)/(2*dis);
double st=atan2(a.x-b.x,a.y-b.y);
double l=acos(t/a.r);
return (line){st-l,st+l};*/
}
vector<line>ve;
int n;
double ans=;
void calc(int x){
for(int i=x+;i<=n;i++){if(cover(c[i],c[x]))return;}//被完全覆盖
ve.clear();
for(int i=x+;i<=n;i++){
if(cover(c[x],c[i]))continue;//完全覆盖
line tmp;
if(c[x].r+c[i].r>Len(c[i]-c[x])) tmp=CX(c[x],c[i]);
else continue;
if(tmp.l<) tmp.l+=*pi;
if(tmp.r<) tmp.r+=*pi;
if(tmp.l>tmp.r){//拆分
ve.push_back((line){,tmp.r});
ve.push_back((line){tmp.l,*pi});
}
else ve.push_back(tmp);
}
sort(ve.begin(),ve.end());
// printf("mid\n");
double now=,ran=;
for(int i=;i<ve.size();i++){//线段覆盖
line tmp=ve[i];
// printf("i:%d %.3f %.3f\n",i,tmp.l,tmp.r);
if(tmp.l>now){ran+=tmp.l-now;now=tmp.r;}
else now=max(now,tmp.r);
}
ran+=*pi-now;
ans+=c[x].r*ran;//累加半径
return;
}
int main(){
freopen("disc.in","r",stdin);
freopen("disc.out","w",stdout);
int i,j;
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%lf%lf%lf",&c[i].r,&c[i].x,&c[i].y);
}
for(i=n;i>=;i--){
calc(i);
// printf("ans:%.3f\n",ans);
}
printf("%.3f\n",ans);
return ;
}