bzoj 1043: [HAOI2008]下落的圆盘

.

题意：n个圆盘从天而降，问最后露在外面的周长
题解：计算几何
QwQ我好菜啊。。我要回去上数学课了。。。
对于每个圆看后面落下的覆盖了它周长的哪些部分，交一下求就好了。
就这题我还打了一个晚上+半个早上，我好菜啊！！
代码：

#include<bits/stdc++.h>
using namespace std;
int n;
const double eps=1e-13;
struct circle
{
    double x,y,r;
    bool del;
    bool operator==(circle a)
    {
        return abs(x-a.x)<eps&&abs(y-a.y)<eps&&abs(r-a.r)<eps;
    }
}a[1010];
double ans=0;
double dis(double x1,double y1,double x2,double y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
pair<double,double> wk(circle x,circle y)
{
    double d=dis(x.x,x.y,y.x,y.y);
    if(d>=(x.r+y.r)*(x.r+y.r)||x.r>y.r&&d<(x.r-y.r)*(x.r-y.r))
    return make_pair(0.0,0.0);
    else if(x.r<y.r&&d-(y.r-x.r)*(y.r-x.r)<eps)
    return make_pair(0.0,2*M_PI);
    double hh=acos((x.r*x.r+d-y.r*y.r)/2/x.r/sqrt(d));
    double oo=acos((y.x-x.x)/sqrt(d));
    if(y.y-x.y>eps)
    oo=2*M_PI-oo;
    double ll=oo-hh,rr=oo+hh;
    if(ll<0)
    ll+=2*M_PI;
    if(rr<0)
    rr+=2*M_PI;
    if(ll-2*M_PI>eps)
    ll-=2*M_PI;
    if(rr-2*M_PI>eps)
    rr-=2*M_PI;
    return make_pair(ll,rr);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf%lf",&a[i].r,&a[i].x,&a[i].y);
        a[i].del=0;
    }
    for(int i=n-1;i>=0;i--)
    {
        vector<pair<double,double> >now;
        now.push_back(make_pair(0.0,0.0));
        bool tf=0;
        for(int j=i+1;j<n;j++)
        {
            if(i==j)
            continue;
            if(a[i]==a[j])
            {
                tf=1;
                break;
            }
            pair<double,double>hh=wk(a[i],a[j]);
            if(hh.first-hh.second>eps)
            {
                now.push_back(make_pair(hh.first,2*M_PI));
                now.push_back(make_pair(0.0,hh.second));
            }
            else
            {
                now.push_back(hh);
            }
            // printf("%g %g\n",hh.first,hh.second);
        }
        if(tf)
        continue;
        sort(now.begin(),now.end());
        vector<pair<double,double> >g;
        g.push_back(now[0]);
        int sz=now.size();
        for(int i=1;i<sz;i++)
        {
            if(g.rbegin()->second-now[i].first>eps)
            g.rbegin()->second=max(g.rbegin()->second,now[i].second);
            else
            g.push_back(now[i]);
        }
        double oo=0;
        sz=g.size();
        for(int i=0;i<sz;i++)
        oo+=g[i].second-g[i].first;
        ans+=a[i].r*(2*M_PI-oo);
        // printf("%.3lf\n",a[i].r*(2*M_PI-oo));
    }
    printf("%.3lf\n",ans);
}