BZOJ 1502：月下柠檬树

BZOJ 1502：月下柠檬树

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1502

题目大意：给出一棵由圆台构成的树以及一个平行光源，问树的阴影面积.

扫描线+自适应Simpson积分

首先给出$Simpson$公式：$int_l^rf(x)dx approx frac{r-l}{6}[f(l)+4f(frac{r-l}{2})+f(r)]$

上述公式只能得出一个近似值，通常情况下与真实值相差甚远，故需要稍加改进为自适应$Simpson$积分：

• 设$mid=frac{r+l}{2}$，分别计算$L=Simpson(int_l^{mid}f(x)dx)$，$R=Simpson(int_{mid}^rf(x)dx)$，$S=Simpson(int_l^rf(x)dx)$.
• 若$L+R=S$，则可以认为$S=int_l^rf(x)dx$；否则用$Simpson$公式递归计算函数在$[l,mid]$和$[mid,r]$的积分.

对于某些不易计算函数积分，能自动调整精度，但误差较大（精度在题目所要求的基础上多加几位），适用于较平滑的曲线；需要注意的是，自适应$Simpson$积分很容易被数据卡掉（毕竟我们只通过$5$个点来大致确定一个图像的面积），故求面积时最好分段。

---

由于题中给出的为平行光，故圆台底面投影在地面上的图形仍为圆。我们将整颗树切分成无数个截面，故树的投影即为无数个圆的投影的面积交，投影图像大致如下：

也就是说，阴影面积即为各个底面以及顶点的投影和两两圆的公切线所围成的面积。

设函数$F(t)$为扫描线$x=t$与上述图形所截的线段长度（显然$F(t)$是连续的），则阴影面积为$int_L^RF(t)dt$，而这个积分可由$Simpson$公式轻松求得.

需要注意的是，若相邻两圆内含，则他们没有公切线。

代码如下：

#include <cstdio>
#include <iostream>
#include <cmath>
#define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)
#define N 505
#define eps 1e-5
using namespace std;
const double inf=1e12;
int n,k;
double alpha,h0,h;
int dcmp(double x){
    if(fabs(x)<eps)return 0;
    else return x<0?-1:1;
}
struct point{
    double x,y;
    point(double X=0,double Y=0){x=X;y=Y;}
};
struct circle{
    point p;
    double r;
    circle(point P=point(0,0),double R=0){p=P;r=R;}
    bool within(circle t){
        return dcmp(fabs(p.x-t.p.x)-fabs(r-t.r))<=0;
    }
}c[N];
struct line{
    point p,q;
    double k,b;
    line(point P=point(0,0),point Q=point(0,0)){
        p=P;q=Q;
        if(p.x>q.x)swap(p,q);
        k=(p.y-q.y)/(p.x-q.x);
        b=p.y-k*p.x;
    }
    double f(double x){
        return k*x+b;
    }
}l[N];
double F(double x){
    double len=0;
    for(int i=0;i<n;++i){//枚举圆与扫描线所截的最大长度
        double d=fabs(c[i].p.x-x);
        if(d-c[i].r<0)len=Max(len,2*sqrt(c[i].r*c[i].r-d*d));
    }
    for(int i=0;i<k;++i)//枚举公切线与扫描线所截的最大长度
        if(l[i].p.x<x&&x<l[i].q.x)len=Max(len,fabs(l[i].f(x))*2);
    return len;
}
double cal(double l,double r){
    double mid=(l+r)/2;
    return (F(l)+4*F(mid)+F(r))*(r-l)/6;
}
double simpson(double l,double r,double s){
    double mid=(l+r)/2;
    double x=cal(l,mid),y=cal(mid,r);
    if(!dcmp(x+y-s))return s;
    else return simpson(l,mid,x)+simpson(mid,r,y);
}
void solve(){
    double L=inf,R=-inf;
    for(int i=0;i<=n;++i){
        L=Min(L,c[i].p.x-c[i].r);
        R=Max(R,c[i].p.x+c[i].r);
    }
    for(int i=1;i<=n;++i){
        if(c[i].within(c[i-1]))continue;//两圆内含的情况
        double sin_theta=(c[i].r-c[i-1].r)/(c[i].p.x-c[i-1].p.x);
        double cos_theta=sqrt(1-sin_theta*sin_theta);
        l[k++]=line(point(c[i].p.x-c[i].r*sin_theta,c[i].r*cos_theta),
                    point(c[i-1].p.x-c[i-1].r*sin_theta,c[i-1].r*cos_theta));
    }
    printf("%.2lf
",simpson(L,R,cal(L,R)));
}
int main(void){
    scanf("%d%lf%lf",&n,&alpha,&h0);
    for(int i=0;i<n;++i){
        c[i].p=point(h0/tan(alpha),0);
        scanf("%lf",&h);
        h0+=h;
    }
    c[n].p=point(h0/tan(alpha),0);c[n].r=0;
    for(int i=0;i<n;++i)scanf("%lf",&c[i].r);
    solve();
}

去掉部分判断语句后，从原来的TLE（6000ms）变成了372ms，不是很懂为什么差距这么大。