BZOJ1043/HAOI2008/下落的圆盘

Posted on By 二价氢

考虑如下的问题:

往数轴上丢若干线段,问最后线段覆盖数轴长度

上面这一题显然是离散化,能在的时间内出解,唔,线段树是吧,那货是的,不考虑,不考虑~

然后考虑下面一题:

往平面直角坐标系内丢若干矩形,问现在从的地方往下看,看到的矩形边界长度为多少

显然,后面丢下去的若干矩形会覆盖前面的矩形,从而使矩形能被看到的边界变小,我们只用枚举矩形即可,最后矩形会变成若干线段,求出这些线段的总长度即可

那么这题不是一样的么?考虑圆,那么它可被覆盖,我们可以求出被覆盖的弧的起始角和终止角,便能求出弧长

所有的圆剩下的弧长和就是答案

如图,我们可以很容易地求出角和角,不需要求交点!!!

然后注意两角跨越坐标轴时的情况即可

AC-Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
using namespace std;
const double EPS=1e-8,INF=1e200,PI=3.1415926535898;
const int MAXN=1005;
typedef pair<double,double> DD;
typedef vector< DD >::iterator Vit;
int n;
double R[MAXN],A[MAXN],B[MAXN],ans,dist;
double alpha,beta,ang,lef,rig;
vector< DD >seg;
DD ptmp;
bool cover;
double Sqr(double x)
{
    return x*x;
}
double Dist(double x1,double y1,double x2,double y2)
{
    return sqrt(Sqr(x1-x2)+Sqr(y1-y2));
}
double angle(double A,double B,double C)
{
    return acos((Sqr(A)+Sqr(B)-Sqr(C))/(2*A*B));//余弦定理
}
int Sign(double x)
{
    if (x>EPS)
        return 1;
    return (0-(x<(-EPS)));
}
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        scanf("%lf%lf%lf",&R[i],&A[i],&B[i]);
    for (int i=0;i<n;i++)
    {
        seg.clear();
        cover=false;
        for (int j=i+1;j<n;j++)
        {
            dist=Dist(A[i],B[i],A[j],B[j]);
            //完全覆盖了
            if (Sign(R[j]-R[i])>=0&&Sign(dist-(R[j]-R[i]))<=0)
            {
                cover=true;
                break;
            }
            //这个圆j在圆i的里面
            if (Sign(dist-(R[j]+R[i]))>=0||Sign(dist-abs(R[j]-R[i]))<=0)
                continue;
            alpha=atan2(B[j]-B[i],A[j]-A[i]);
            beta=angle(R[i],dist,R[j]);
            ptmp=make_pair(alpha-beta,alpha+beta);
            if (Sign(ptmp.first)<=0&&Sign(ptmp.second)<=0)
                seg.push_back(make_pair(2*PI+ptmp.first,2*PI+ptmp.second));
            else if (Sign(ptmp.first<0))
            {
                seg.push_back(make_pair(2*PI+ptmp.first,2*PI));
                seg.push_back(make_pair(0,ptmp.second));
            }
            else
                seg.push_back(ptmp);
        }
        if (cover)
            continue;
        seg.push_back(make_pair((double)10.0,(double)10.0));
        sort(seg.begin(),seg.end());
        ang=lef=rig=0;
        for (Vit it=seg.begin();it!=seg.end();it++)
        {
            if (Sign(rig-it->first)>=0)
                rig=max(rig,it->second);
            else
            {
                ang+=rig-lef;
                lef=it->first;
                rig=it->second;
            }
        }
        ans+=R[i]*(2*PI-ang);
    }
    printf("%.3lf\n",ans);
}
/*
 * 计算几何毁一生
 */