BZOJ 1043 [HAOI2008]下落的圆盘

三角函数计算+区间合并

对于每一个圆，判断接下来掉落的圆是否会覆盖它，用余弦定理之类的三角函数搞一搞就好了。计算出被覆盖的角的区间，然后并一下。

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 1005
using namespace std;
struct circle
{
    double r, x, y;
}c[N];
struct interval
{
    double l, r;
}inter[N<<1];
const double eps = 1e-7, pi = acos(-1.0);
int icnt;
bool cmp(interval a, interval b){return a.l<b.l||(a.l==b.l&&a.r>b.r);}
void solve(circle a, circle b)
{
    double dis=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    if(dis>=a.r+b.r+eps)return;

    if(dis<=b.r-a.r+eps)
    {
        inter[++icnt]=(interval){-pi,pi};
        return;
    }

    if(dis<=a.r-b.r+eps)
        return;
    double angle = atan2(b.y-a.y,b.x-a.x);
    double angle2 = acos( (dis*dis+a.r*a.r-b.r*b.r)/(2*a.r*dis) );
    double la = angle-angle2, ra = angle+angle2;
    if(la<-pi)
    {
        inter[++icnt]=(interval){la+2*pi,pi};
        inter[++icnt]=(interval){-pi,ra};
    }
    else if(ra>pi)
    {
        inter[++icnt]=(interval){la,pi};
        inter[++icnt]=(interval){-pi,ra-2*pi};
    }
    else inter[++icnt]=(interval){la,ra};
}
int main()
{
    int n;
    double ans=0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        scanf("%lf%lf%lf",&c[i].r,&c[i].x,&c[i].y);
    for(int i = 1; i <= n; i++)
    {
        icnt=0;
        for(int j = i+1; j <= n; j++)
            solve(c[i],c[j]);
        sort(inter+1,inter+1+icnt,cmp);
        double lost=0, left=inter[1].l, right=inter[1].r;
        for(int j = 2; j <= icnt; j++)
        {
            if(inter[j].l>left)
            {
                if(inter[j].l>right)
                {
                    lost+=right-left;
                    left=inter[j].l;
                    right=inter[j].r;
                }
                else if(right<inter[j].r)right=inter[j].r;
            }
        }
        if(icnt)lost+=right-left;
        if(lost<2*pi)ans+=c[i].r*(2*pi-lost);
    }
    printf("%.3lf",ans);
    return 0;
}