首页 > 代码库 > 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: 圆的面积并
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。