首页 > 代码库 > bzoj1043 下落的圆盘
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(-1.l),_2pi=pi*2;struct itv{ld l,r;};bool operator<(itv x,itv y){return x.l<y.l;}int ip=0;ld ans=0;void maxs(ld&a,ld b){if(a<b)a=b;}itv is[2007];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-8<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-8&&c>fabs(r-w.r)+1e-8; } 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}; } void get(){ std::sort(is,is+ip); ld L,R,s=_2pi; for(int i=0,j=0;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[1007];int main(){ scanf("%d",&n); for(int i=0;i<n;++i)cs[i].init(); for(int i=0;i<n;++i){ ip=0; for(int j=i+1;j<n;++j)if(cs[i].in(cs[j]))goto out; for(int j=i+1;j<n;++j)if(cs[i].cross(cs[j]))cs[i].cal(cs[j]); cs[i].get(); out:; } printf("%.3f",ans); return 0;}
bzoj1043 下落的圆盘
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。