欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[BZOJ1502][NOI2005]月下柠檬树(辛普森积分+解析几何)

程序员文章站 2024-02-21 18:50:58
...

题目:

我是超链接

题解:

首先我们理解一下投影的性质,也就是投影出来的图形一定跟原图形全等。
考虑一下圆形投影下来是什么呢?和原来一样的圆形啊

怎么转化竖着的树呢?
[BZOJ1502][NOI2005]月下柠檬树(辛普森积分+解析几何)

也就是树高*cot(α)

那么我们所要求的就是一些圆形和一些等腰梯形面积并

样例图片是这样的
[BZOJ1502][NOI2005]月下柠檬树(辛普森积分+解析几何)

那么运用计算几何的知识就可以得到圆的方程和圆的公切线的方程,然后得到一个连续的函数(这样用辛普森积分的时候就不必考虑将整个图形拆成若干个一坨一坨的图形再求积分)。最后这个题就成为一个函数的解析式,这个函数关于x轴对称,求这个函数与X轴之间的面积,因为对称,*2就行了

微积分啊。

套用辛普森积分:Simpson(l,r) = (F(l) + F(r) + F(mid) * 4) * (r - l) / 6.0,然后递归检查精度,如果左值+右值-总值的绝对值小于精度就返回,否则就递归返回左侧面积和右侧面积。得到一个近似精确的值就是所求的答案。

辛普森积分:不能求出精确解,但是可以近似地求出一些微积分不能够求解的图像的面积。

代码:

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=1005;
const double eps=1e-6;
int n;
struct hh{
    double x,y;
    hh(double X=0,double Y=0){x=X;y=Y;}
}a[N],s[N],e[N];
double pf(double x){return x*x;}
void cl(int i)
{
    if (fabs(a[i+1].y-a[i].y)<eps){e[i]=a[i+1];s[i]=a[i];return;}
    double si=(a[i+1].y-a[i].y)/(a[i+1].x-a[i].x);
    e[i].x=a[i+1].x-a[i+1].y*si;
    e[i].y=sqrt(pf(a[i+1].y)-pf(a[i+1].y*si));
    s[i].x=a[i].x-a[i].y*si;
    s[i].y=sqrt(pf(a[i].y)-pf(a[i].y*si));
}
double f(double x)//在x位置最大的y值,也就是在表面上的值 
{
    double y=0;
    for (int i=1;i<=n+1;i++)
        if (fabs(a[i].x-x)<=a[i].y)//圆内
          y=max(y,sqrt(pf(a[i].y)-pf(a[i].x-x)));
    for (int i=1;i<=n;i++)
        if (a[i+1].x-a[i].x+a[i].y>a[i+1].y && x<=e[i].x && x>=s[i].x)
          y=max(y,(e[i].y-s[i].y)/(e[i].x-s[i].x)*(x-s[i].x)+s[i].y);
    return y;
}
double work(double L ,double R)
{
    double mid=(L+R)/2;
    return (f(L)+f(R)+f(mid)*4)*(R-L)/6;
}
double Simpson(double L,double R)
{
    double mid=(L+R)/2;
    double x1=work(L,mid),x2=work(mid,R),x3=work(L,R);
    if (fabs(x1+x2-x3)<eps) return x1+x2;
    else return Simpson(L,mid)+Simpson(mid,R);
}
int main()
{
    double tha;
    scanf("%d%lf",&n,&tha);
    tha=1/tan(tha);
    double h=0;
    for (int i=1;i<=n+1;i++)
    {
        double x;scanf("%lf",&x);
        h+=x; a[i].x=tha*h;
    }
    for (int i=1;i<=n;i++) scanf("%lf",&a[i].y);
    double L=a[1].x,R=a[n+1].x;
    for (int i=1;i<=n;i++) 
    {
        L=min(L,a[i].x-a[i].y);
        R=max(R,a[i].x+a[i].y);
        if (a[i+1].x-a[i].x+a[i].y>a[i+1].y) cl(i);
    }
    printf("%.2lf",2*Simpson(L,R));
}