bzoj1043 下落的圆盘

Description

　　有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红
色线条的总长度即为所求. 

Input

　　第一行为1个整数n,N<=1000
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.

Output

　　最后的周长，保留三位小数

对每个圆，若没被后面的圆完全覆盖，就统计后面的圆覆盖的圆周长度，具体实现可以求出圆周上每个被覆盖区间并取并

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

typedef double ld;

int n;

const ld pi=acos(-.l),_2pi=pi*;

struct itv{ld l,r;};

bool operator<(itv x,itv y){return x.l<y.l;}

int ip=;

ld ans=;

void maxs(ld&a,ld b){if(a<b)a=b;}

itv is[];

struct cir{

    ld x,y,r;

    void init(){

        scanf("%lf%lf%lf",&r,&x,&y);

    }

    bool in(cir w){

        ld a=x-w.x,b=y-w.y;

        return sqrt(a*a+b*b)+r-1e-<w.r;

    }

    bool cross(cir w){

        ld a=x-w.x,b=y-w.y;

        ld c=sqrt(a*a+b*b);

        return c<r+w.r-1e-&&c>fabs(r-w.r)+1e-;

    }

    ld fix(ld x){

        while(x<)x+=_2pi;

        while(x>_2pi)x-=_2pi;

        return x;

    }

    void cal(cir w){

        ld xd=w.x-x,yd=w.y-y,d=sqrt(xd*xd+yd*yd);

        ld a=atan2(yd,xd);

        ld b=acos((r*r+d*d-w.r*w.r)/(*r*d));

        ld l=fix(a-b),r=fix(a+b);

        if(l<r)is[ip++]=(itv){l,r};

        else is[ip++]=(itv){,r},is[ip++]=(itv){l,_2pi};

    }

    void get(){

        std::sort(is,is+ip);

        ld L,R,s=_2pi;

        for(int i=,j=;i<ip;i=j){

            L=is[i].l;R=is[i].r;

            while(j<ip&&is[j].l<=R)maxs(R,is[j++].r);

            s-=R-L;

        }

        ans+=s*r;

    }

}cs[];

int main(){

    scanf("%d",&n);

    for(int i=;i<n;++i)cs[i].init();

    for(int i=;i<n;++i){

        ip=;

        for(int j=i+;j<n;++j)if(cs[i].in(cs[j]))goto out;

        for(int j=i+;j<n;++j)if(cs[i].cross(cs[j]))cs[i].cal(cs[j]);

        cs[i].get();

        out:;

    }

    printf("%.3f",ans);

    return ;

}