【bzoj1043】[HAOI2008]下落的圆盘

2015.05.25 09:54 Mon | 8次阅读 | 旧日oi | 固定链接 | 源码

题目大意:先后在一个平面上放n个圆,后放的会盖住先放的,求最后所有圆的可见周长之和 n<=1000
题解
对于每个圆,我们只需考虑后面与它相交的圆,求出相交的总弧长就好了,也可以用弧度来表示。
如果两个圆相交,那么两圆连心线的极角就是斜率,两圆相交的半弧长对应每个圆的弧度可以用余弦定理求,这里自己推一下就好了。
把所有的相交弧度存到一个队列里,处理一下负弧度,并把跨越正负的区间分成两段之后按起点排序扫一遍就可以求出没被覆盖的总弧长对应的弧度了。

我的程序

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const double pi=acos(-1);
struct Cir{
    double r,x,y;
}c[1005];
struct Hu{
    double l,r;
    Hu(double _,double __):l(_),r(__){}
    Hu(){}
}q[2005];
int n,top;
double dis(int a,int b)
{
    return sqrt((c[a].x-c[b].x)*(c[a].x-c[b].x)+(c[a].y-c[b].y)*(c[a].y-c[b].y));
}
bool in(int x,int y)
{
    if(c[y].r-c[x].r>=dis(x,y)) return 1;
    return 0;
}
void work(int a,int b)
{
    double mid=atan2((c[b].y-c[a].y),(c[b].x-c[a].x));
    double len=acos((c[a].r*c[a].r+dis(a,b)*dis(a,b)-c[b].r*c[b].r)/(2*c[a].r*dis(a,b)));
    q[++top]=Hu(mid-len,mid+len);
}
bool cmp(const Hu &a,const Hu &b)
{
    return a.l<b.l;
}
double calc(int x)
{
    for(int i=x+1;i<=n;i++) if(in(x,i)) return 0;
    top=0;
    for(int i=x+1;i<=n;i++)
    if(!in(i,x)&&c[i].r+c[x].r>dis(i,x)) work(x,i);
    double tmp=0,now=0;
    for(int i=1;i<=top;i++)
    {
        if(q[i].l<0) q[i].l+=2*pi;
        if(q[i].r<0) q[i].r+=2*pi;
        if(q[i].l>q[i].r)
        {
            q[++top]=Hu(0,q[i].r);
            q[i].r=2*pi;
        }
    }
    sort(q+1,q+top+1,cmp);
    for(int i=1;i<=top;i++)
    {
        if(q[i].l>now)
        {
            tmp+=q[i].l-now;
            now=q[i].r;
        }
        else now=max(now,q[i].r);
    }
    tmp+=2*pi-now;
    return  c[x].r*tmp;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&c[i].r,&c[i].x,&c[i].y);
    double ans=0;
    for(int i=1;i<=n;i++) ans+=calc(i);
    printf("%.3lf\n",ans);
}```