bzoj1043 下落的圆盘 [线段覆盖]

in 题目 with 0 comment

Description

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


Input

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


Output

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


Sample Input

2
1 0 0
1 1 0


Sample Output

10.472


Solution

其实就是线段覆盖问题,麻烦一点的就是圆与圆之间覆盖的圆心角的问题.由于数据范围$n\le 1000$,我们可以枚举每一个点,计算它被在他之后落下的圆盘覆盖住的圆心角即可,怎么算呢?对于任意两个相交的圆,其被覆盖的圆心角度数由余弦定理很好求得,为$acos((r_a^2+d^2-r_b^2)/(2r_ad))$,圆心角范围再加上两圆圆心连线的极角即可.最后贪心地求线段覆盖.


Code

#include<bits/stdc++.h>
#define maxn 2500
#define pi acos(-1.0)
//#define DEBUG
using namespace std;
int n,tot;
double ans=0;

struct circle
{
    double r,x,y;
    circle(double r=0,double x=0,double y=0):r(r),x(x),y(y) {}
}o[maxn];

struct section
{
    double l,r;
    section(double l=0,double r=0):l(l),r(r) {}
    bool operator < (const section rhs) const
    {
        return l<rhs.l;
    }
}s[maxn];

double dis(int a,int b)
{
    return sqrt((o[a].x-o[b].x)*(o[a].x-o[b].x)+(o[a].y-o[b].y)*(o[a].y-o[b].y));
}

bool cover(int a,int b)
{
    if(o[a].r+dis(a,b)<=o[b].r) return 1;
    return 0;
}

void seg(int a,int b)
{
    double d=dis(a,b);
    double t=acos((o[a].r*o[a].r+d*d-o[b].r*o[b].r)/(2*o[a].r*d));
    double st=atan2(o[a].x-o[b].x,o[a].y-o[b].y);
    s[++tot]=section(st-t,st+t); 
}

double cal(int x)
{
    tot=0;
    for(int i=x+1;i<=n;++i)
        if(cover(x,i)) return 0;
    for(int i=x+1;i<=n;++i)
        if(!cover(i,x)&&o[x].r+o[i].r>dis(x,i))
            seg(x,i);
    double tmp=0,now=0;
    for(int i=1;i<=tot;++i)
    {
        if(s[i].l<0) s[i].l+=2*pi;
        if(s[i].r<0) s[i].r+=2*pi;
        if(s[i].l>s[i].r)
        {
            s[++tot]=section(0,s[i].r);
            s[i].r=2*pi;
        }
    }
    sort(s+1,s+tot+1);
    for(int i=1;i<=tot;++i)
    {
        if(now<s[i].l)
        {
            tmp+=s[i].l-now;
            now=s[i].r;
        }
        else now=max(now,s[i].r);
    }
    tmp+=2*pi-now;
    return o[x].r*tmp;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lf%lf%lf",&o[i].r,&o[i].x,&o[i].y);
    for(int i=1;i<=n;++i) ans+=cal(i);
    printf("%.3lf\n",ans);
    return 0;
} 

扫描二维码,在手机上阅读!
Responses