UOJ Logo zhouzixuan的博客

博客

bzoj 1502: [NOI2005]月下柠檬树

2015-11-29 20:47:08 By zhouzixuan
【题目描述】:

【题目解法】:
    首先既然是平行光,那么投影的图形应该与原图形相同
    因此就变成了这样(转自Claude的blog)

    也就是一堆圆和梯形的面积并
    我们直接上自适应simpson求积分就好了
    simpson是牛顿科斯特公式当n=2时的情况,相当于二次函数求积分面积
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int N=505;
const double zero=1e-8;
const double INF=1e15;
struct LineNode {double ax,ay,bx,by;} line[N];
struct CircleNode {double s,r;} circle[N];
int n,tot; double h[N],alphi,ans,L,R;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    n=getint()+1; scanf("%lf",&alphi); R=0; L=INF;
    for (int i=1; i<=n; i++) scanf("%lf",&h[i]);
    for (int i=1; i<=n; i++) h[i]+=h[i-1];
    for (int i=1; i<=n-1; i++)
    {
        scanf("%lf",&circle[i].r);
        circle[i].s=h[i]/tan(alphi);
    }
    circle[n].s=h[n]/tan(alphi);
    for (int i=1; i<=n; i++) L=min(L,circle[i].s-circle[i].r);
    for (int i=1; i<=n; i++) R=max(R,circle[i].s+circle[i].r);
}
void prepare()
{
    for (int i=1,j=2; i<n; i++,j++)
    {
        if (circle[j].s-circle[i].s<=fabs(circle[i].r-circle[j].r)) continue; ++tot;
        line[tot].ax=circle[i].s-circle[i].r*(circle[j].r-circle[i].r)/(circle[j].s-circle[i].s);
        line[tot].bx=circle[j].s-circle[j].r*(circle[j].r-circle[i].r)/(circle[j].s-circle[i].s);
        line[tot].ay=sqrt(sqr(circle[i].r)-sqr(line[tot].ax-circle[i].s));
        line[tot].by=sqrt(sqr(circle[j].r)-sqr(line[tot].bx-circle[j].s));
    }
}
inline double F(double x)
{
    double nowans=0;
    for (int i=1; i<=n; i++)
    {
        if (fabs(x-circle[i].s)>circle[i].r) continue;
        nowans=max(nowans,sqrt(sqr(circle[i].r)-sqr(x-circle[i].s)));
    }
    for (int i=1; i<=tot; i++)
    {
        if ((x<line[i].ax)||(x>line[i].bx)) continue;
        double k=(line[i].by-line[i].ay)/(line[i].bx-line[i].ax);
        nowans=max(nowans,k*(x-line[i].ax)+line[i].ay);
    }
    return nowans;
}
double simpson(double l,double r)
{
    double mid=(l+r)/2.0;
    return (F(l)+4*F(mid)+F(r))*(r-l)/6.0;
}
double Simpson(double l,double r,double pre)
{
    double mid=(l+r)/2.0;
    double Ls=simpson(l,mid),Rs=simpson(mid,r);
    if (fabs(pre-Ls-Rs)<=zero) return pre;
    return Simpson(l,mid,Ls)+Simpson(mid,r,Rs);
}
int main()
{
    init();
    prepare();
    printf("%.2lf\n",2*Simpson(L,R,simpson(L,R)));
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。