[Solution][Computational geometry][Simpson integration]NOI2005 月下柠檬树

【题目】

戳这里

【题意】

给出一个圆锥及其下面的若干圆柱,求出给定角度的光线将组合体投影到水平面上的投影大小。

【思路】

据称是Simpson积分裸题,但是好像当年的题解是无比神奇的分类讨论。。。

首先考虑水平面上投影的形状。
把组合体分解成若干个大小不等的圆,则投影可看作这些圆投影出的圆的面积叠加。
则最终的图形必然是由相邻两个连接处的圆及其公切线围成的图形组成的。
因此就有了求F函数的方法。
对于一个横坐标,暴力枚举所有圆和合法公切线,维护其纵坐标最大值返回。
边界问题:左右边界不一定是最下面的圆和最上面的圆!
这样就可以直接套公式了。

【代码】

/**************************************************************
    Problem: 1502
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:592 ms
    Memory:872 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<cstring>
const double INF = 10000000.0;
inline double _abs(double x)
{
    return x > 0 ? x : -x;
}
inline double _max(double x , double y)
{
    return x > y ? x : y;
}
int n;
double r[1001] , h[1001] , ins[1001];
struct Seg
{
    double from , to , k , fromh;
    void read(int d1 , int d2 , int d3 , int d4)
    {
        from = d1;
        to = d2;
        k = d3;
        fromh = d4;
    }
}S[1001];
int Seg_num;
double F(double x)
{
    int i;
    double max = -INF , high;
    for(i = 1 ; i <= n ; ++i)
    {
        if (x> ins[i] - r[i] && x < ins[i] + r[i])
        {
            high = sqrt((r[i] * r[i]) - (x - ins[i]) * (x - ins[i]));
            max = _max(max , high);
        }
    }
    for(i = 1 ; i <= Seg_num ; ++i)
    {
        if (x> S[i].from && x < S[i].to)
        {
            high = S[i].fromh + (x - S[i].from) * S[i].k;
            max = _max(max , high);
        }
    }
    return max;
}
inline double simpson(double l , double r)
{
    double mid = l + (r - l) / 2;
    return (F(l) + 4 * F(mid) + F(r)) * (r - l) / 6.0;
}
inline double asr(double l , double r , double eps , double A)
{
    double mid = l + (r - l) / 2;
    double simpl = simpson(l , mid);
    double simpr = simpson(mid , r);
    if (_abs(simpl + simpr - A) <= 15.0 * eps)
        return simpl + simpr + (simpl + simpr - A) / 15.0;
    return asr(l , mid , eps/2 , simpl) + asr(mid , r , eps/2 , simpr);
}
int main()
{
    double alpha;
    scanf("%d%lf" , &n , &alpha);
    double Tan = tan(alpha);
    register int i;
    for(i = 0 ; i <= n ; ++i)
        scanf("%lf" , &h[i]);
    h[n + 1] = 0;
    for(i = 1 ; i <= n ; ++i)
        scanf("%lf" , &r[i]);
    double L = INF , R = -INF;
    double now_h = h[0];
    for(i = 1 ; i <= n + 1 ; ++i)
    {
        ins[i] = now_h / Tan;
        if (L > ins[i] - r[i])
            L = ins[i] - r[i];
        if (R < ins[i] + r[i])
            R = ins[i] + r[i];
        now_h += h[i];
    }
    for(i = 1 ; i <= n ; ++i)
    {
        if (r[i] == r[i + 1])
            S[++Seg_num].read(ins[i] , ins[i + 1] , 0 , r[i]);
        else if (r[i] > r[i + 1])
        {
            if (r[i] - r[i + 1] > ins[i + 1] - ins[i])
                continue;
            double Cos = (r[i] - r[i + 1]) / (ins[i + 1] - ins[i]);
            alpha = acos(Cos);
            S[++Seg_num].from = ins[i] + r[i] * cos(alpha);
            S[Seg_num].to = ins[i + 1] + r[i + 1] * cos(alpha);
            S[Seg_num].k = (r[i] - r[i + 1]) * sin(alpha) / (S[Seg_num].from - S[Seg_num].to);
            S[Seg_num].fromh = r[i] * sin(alpha);
        }
        else
        {
            if (r[i + 1] - r[i] > ins[i + 1] - ins[i])
                continue;
            double Cos = (r[i + 1] - r[i]) / (ins[i + 1] - ins[i]);
            alpha = acos(Cos);
            S[++Seg_num].from = ins[i] - r[i] * cos(alpha);
            S[Seg_num].to = ins[i + 1] - r[i + 1] * cos(alpha);
            S[Seg_num].k = (r[i + 1] - r[i]) * sin(alpha) / (S[Seg_num].to - S[Seg_num].from);
            S[Seg_num].fromh = r[i] * sin(alpha);
        }
    }
    printf("%.2lf" , 2 * asr(L , R , 1e-3 , simpson(L , R)));
    return 0;
}
comments powered by Disqus