洛谷P4207 [NOI2005]月下柠檬树

我是月下柠檬精

毒瘤初中数学题加个自适应辛普森积分板子？

题目大意：一堆圆台，给定平行光角度\(a\)，问影子面积

考虑清楚：圆一点不变，梯形高度变为原来的\(\frac{1}{tan(a)}\)

然后求出每一段切线的解析式直接用辛普森日

请自行脑补一万行初中知识推理……我懒得写了

顺便扔个讲的清楚的博客跑了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
namespace red{
#define y1 qwq
#define Eps (1e-6)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int N=1010;
    int n;
    double arf,l,rr;
    double h[N],r[N];
    struct seg
    {
        double k,b,l,r;
    }q[N];
    inline double gg(double a,double b)
    {
        return sqrt(a*a-b*b);
    }
    inline void get_seg(int x,int y)
    {
        if(fabs(r[x]-r[y])<Eps)
        {
            q[x].l=h[x];q[x].r=h[y];
            q[x].k=0,q[x].b=r[x];
            return;
        }
        double dx=h[y]-h[x],dr=fabs(r[x]-r[y]);
        if(r[x]>r[y])
        {
            q[x].l=h[x]+r[x]*dr/dx;
            q[x].r=h[y]+(q[x].l-h[x])*r[y]/r[x];
            double tl=gg(r[x],q[x].l-h[x]);
            double tr=gg(r[y],q[x].r-h[y]);
            q[x].k=(tl-tr)/(q[x].l-q[x].r);
            q[x].b=tl-q[x].l*q[x].k;
        }
        else
        {
            q[x].r=h[y]-r[y]*dr/dx;
            q[x].l=h[x]-(h[y]-q[x].r)*r[x]/r[y];
            double tl=gg(r[x],q[x].l-h[x]);
            double tr=gg(r[y],q[x].r-h[y]);
            q[x].k=(tl-tr)/(q[x].l-q[x].r);
            q[x].b=tl-q[x].l*q[x].k;
        }
    }
    inline double f(double x)
    {
        double ans=0;
        for(int i=1;i<=n;++i)
        {
            if(x<h[i]+r[i]&&x>h[i]-r[i]) ans=max(ans,gg(r[i],x-h[i]));
            if(x>=q[i].l&&x<=q[i].r) ans=max(ans,q[i].k*x+q[i].b);
        }
        return ans;
    }
    inline double simpson(double l,double r)
    {
        double mid=(l+r)/2;
        return (f(l)+4*f(mid)+f(r))*(r-l)/6;
    }
    inline double adapative(double l,double r,double eps,double ans)
    {
        double mid=(l+r)/2;
        double tl=simpson(l,mid),tr=simpson(mid,r);
        if(fabs(tl+tr-ans)<=15*eps) return (tl+tr)+(tl+tr-ans)/15;
        return adapative(l,mid,eps/2,tl)+adapative(mid,r,eps/2,tr);
    }
    inline void main()
    {
        n=read();
        scanf("%lf",&arf);
        arf=1.0/tan(arf);
        for(int i=1;i<=n+1;++i)
        {
            scanf("%lf",&h[i]);
            h[i]*=arf;
            if(i^1) h[i]+=h[i-1];
        }
        for(int i=1;i<=n;++i) scanf("%lf",&r[i]);
        ++n;
        for(int i=1;i<n;++i) get_seg(i,i+1);
        l=h[1]-r[1],rr=h[n];
        for(int i=1;i<=n;++i)
        {
            l=min(l,h[i]-r[i]);
            rr=max(rr,h[i]+r[i]);
        }
        printf("%.2f\n",adapative(l,rr,1e-6,simpson(l,rr))*2);
    }
}
signed main()
{
    red::main();
    return 0;
}

洛谷P4207 [NOI2005]月下柠檬树

原文：https://www.cnblogs.com/knife-rose/p/12174763.html