首页 > 代码库 > bzoj2178: 圆的面积并

bzoj2178: 圆的面积并

Description

给出N个圆,求其面积并

Input

先给一个数字N ,N< = 1000 接下来是N行是圆的圆心,半径,其绝对值均为小于1000的整数

Output

面积并,保留三位小数
简单说就是去除被包含的圆,求出每个圆的圆周未被其他圆覆盖的圆弧,求对应弓形的面积以及弓形的弦与原点构成的三角形的有向面积。
#include<cstdio>#include<cmath>#include<algorithm>using namespace std;typedef long double ld;int n;const ld pi=acos(-1.l),_2pi=pi*2;struct itv{ld l,r;}is[2007];bool operator<(itv x,itv y){return x.l<y.l;}int ip;ld ans=0;ld maxs(ld&a,ld b){if(a<b)a=b;}struct cir{    int x,y,r;    void init(){scanf("%d%d%d",&x,&y,&r);}    bool in(cir w){        int a=x-w.x,b=y-w.y;        return sqrt(a*a+b*b)+r-1e-7l<w.r;    }    bool cross(cir w){        int a=x-w.x,b=y-w.y;        return sqrt(a*a+b*b)<r+w.r;    }    ld fix(ld x){        while(x<0)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)/(2*r*d));        ld l=fix(a-b),r=fix(a+b);        if(l<r)is[ip++]=(itv){l,r};        else is[ip++]=(itv){0,r},is[ip++]=(itv){l,_2pi};    }    inline void g1(ld a){        ans+=(a-sin(a))*r*r;    }    inline void g2(ld L,ld R){        ans+=((x+cos(L)*r)*(y+sin(R)*r)-(x+cos(R)*r)*(y+sin(L)*r));    }    void get(){        if(!ip){            ans+=pi*r*r*2;            return;        }        std::sort(is,is+ip);        ld L,R=-1,R1;        for(int i=0,j=0;i<ip;i=j){            R1=R;L=is[i].l;R=is[i].r;            while(j<ip&&is[j].l<=R)maxs(R,is[j++].r);            if(R1!=-1)g1(L-R1),g2(R1,L);        }        g1(is[0].l+_2pi-R),g2(R,is[0].l+_2pi);    }}cs[1007];int main(){    scanf("%d",&n);    for(int i=0;i<n;++i)cs[i].init();    for(int i=0;i<n;++i){        for(int j=0;j<n;++j)if(i!=j&&cs[i].in(cs[j])){            cs[i--]=cs[--n];            break;        }    }    for(int i=0;i<n;++i){        ip=0;        for(int j=0;j<n;++j)if(i!=j&&cs[i].cross(cs[j])){            cs[i].cal(cs[j]);        }        cs[i].get();    }    printf("%.3Lf",ans/2.);    return 0;}

 

bzoj2178: 圆的面积并