BZOJ1043:[HAOI2008]下落的圆盘 计算几何+离线处理

思路:

嗯,我诅咒你,出题人,持续一辈子的呦~~

我们考虑每个圆对于最终答案的贡献,显然就是将所有在之后的圆覆盖在这个圆上的部分去掉,剩下的若干段弧长.

那么接下来就是找出对于一个圆,他有哪些部分是被覆盖的.

我们对于每一个后面的圆,找出他覆盖在这个圆上面的极角序区间,最后我们再求一次区间的并就可以了.

找出这段区间成为了这道题目的难点.

首先我们找出两个圆的交点.什么你不会?

看下面的图片:(假设是圆\(O_2\)覆盖圆\(O_1\))

(看不清楚图片请点击一下放大来看)求出\(a,b\)之后,就很容易利用向量求出两个交点坐标了.(具体怎么求就不要问我了吧QoQ)

然后我们确定这两个点关于点\(O_1\)的极角序,但是究竟是由哪一个指向哪一个呢?

我们只要再确定点\(O_2\)关于圆心\(O_1\)的极角序,并保证上述的区间经过这个位置即可.

具体的细节就只能自己体会了.可以参照我的代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
inline f2 sqr(const f2&x){
    return x*x; 
}
static const f2 PI=acos(-1.0);
 
#define N 1010
struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
};
f2 dist(const Point&A,const Point&B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
 
typedef Point vector;
inline vector Getvertical(vector _v){return vector(-_v.y,_v.x);}
inline f2 Getlength(vector _v){return sqrt(sqr(_v.x)+sqr(_v.y));}
inline vector Getunitvector(vector _v){
    f2 length=Getlength(_v);
    return vector(_v.x/length,_v.y/length);
}
 
struct Circle{
    Point o;f2 r;
    Circle(){}
    Circle(Point _o,f2 _r):o(_o),r(_r){}
    f2 get(const Point&B)const{return atan2(B.y-o.y,B.x-o.x);}
}C[N];
inline bool IsIntersect(const Circle&A,const Circle&B){
    return A.r+B.r>dist(A.o,B.o);
}
inline bool IsCover(const Circle&A,const Circle&B){
    return A.r>=B.r&&dist(A.o,B.o)<=A.r-B.r;
}
 
struct Interval{
    f2 l,r;
    Interval(){}
    Interval(f2 _l,f2 _r):l(_l),r(_r){}
    bool operator<(const Interval&B)const{return l<B.l;}
}S[N<<1];int id;
inline bool find(f2 l,f2 r,f2 x){
	if(l<=r)return x>=l&&x<=r;else return x>=l||x<=r;
}
inline void add(f2 l,f2 r){
    if(l<=r)S[++id]=Interval(l,r);else S[++id]=Interval(l,PI),S[++id]=Interval(-PI,r);
}
 
int main(){
    int n;scanf("%d",&n);
    register int i,j,k;
    for(i=1;i<=n;++i){
        scanf("%lf%lf%lf",&C[i].r,&C[i].o.x,&C[i].o.y);
    }
    f2 totans=0,a,b,d,ang1,ang2,ango;Point p1,p2; 
    vector v,_v;
    for(i=n;i>=1;--i){
        bool cover=0;id=0;
        for(j=i+1;j<=n&&!cover;++j)if(IsCover(C[j],C[i]))cover=1;
        if(!cover){
            for(j=i+1;j<=n;++j)if(IsIntersect(C[i],C[j])&&!IsCover(C[i],C[j])){
                d=dist(C[i].o,C[j].o);
                b=(sqr(C[i].r)-sqr(C[j].r)+sqr(d))/(2*d);
                a=sqrt(sqr(C[i].r)-sqr(b));
                v=C[i].o-C[j].o,_v=Getunitvector(Getvertical(v));
                p1=C[i].o+v*(b/d)+_v*a,p2=C[i].o+v*(b/d)+_v*(-a);
                ang1=C[i].get(p1),ang2=C[i].get(p2),ango=C[i].get(C[j].o);
                if(find(ang1,ang2,ango))add(ang1,ang2);else add(ang2,ang1);
            }
            totans+=2*PI*C[i].r;
            if(id){
                sort(S+1,S+id+1);
                f2 Maxr;
                for(j=1;j<=id;){
                    for(Maxr=S[j].r,k=j+1;k<=id;++k){
                        if(S[k].l>Maxr)break;
                        if(S[k].r>Maxr)Maxr=S[k].r;
                    }
                    totans-=C[i].r*(Maxr-S[j].l);
                    j=k;
                }
            }
        }
    }
    printf("%.3lf",totans);
    return 0;
}