BZOJ 1502: [NOI2005]月下柠檬树 [辛普森积分解析几何圆]

1502: [NOI2005]月下柠檬树

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1070 Solved: 596
[Submit][Status][Discuss]

Description

BZOJ 1502: [NOI2005]月下柠檬树 [辛普森积分解析几何圆]-LMLPHP

Input

文件的第1行包含一个整数n和一个实数alpha，表示柠檬树的层数和月亮的光线与地面夹角(单位为弧度)。第2行包含n+1个实数h0,h1,h2,…,hn，表示树离地的高度和每层的高度。第3行包含n个实数r1,r2,…,rn，表示柠檬树每层下底面的圆的半径。上述输入文件中的数据，同一行相邻的两个数之间用一个空格分隔。输入的所有实数的小数点后可能包含1至10位有效数字。

Output

输出1个实数，表示树影的面积。四舍五入保留两位小数。

Sample Input

2 0.7853981633
10.0 10.00 10.00
4.00 5.00

Sample Output

171.97

HINT

1≤n≤500，0.3

我一定是在做数学！！！！

%%%Claude画图真好看 http://blog.csdn.net/wzq_qwq/article/details/48310417

把每条线段和每个点的投影找出来，然后计算F函数时遍历所有线段和圆找最大值行了

这里的线保存了k和b，解析几何的感觉

找点和圆的切线用了射影定理，小新讲过然而并不会(因为我只会三角形相似)，又去学了一下

找圆的公切线直接用三角函数....

//

//  main.cpp

//  bzoj1502

//

//  Created by Candy on 2017/2/1.

//  Copyright © 2017年 Candy. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

typedef long long ll;

const int N=;

const double INF=1e9;

const double eps=1e-;

const double pi=acos(-);

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

inline int sgn(double x){

    if(abs(x)<eps) return ;

    else return x<?-:;

}

struct Vector{

    double x,y;

    Vector(double a=,double b=):x(a),y(b){}

    void print(){printf("%lf %lf\n",x,y);}

};

typedef Vector Point;

struct Line{

    Point s,t;

    double k,b;

    Line(){}

    Line(Point a,Point c):s(a),t(c){

        k=(t.y-s.y)/(t.x-s.x);

        b=s.y-k*s.x;

    }

    double f(double x){return k*x+b;}

}L[N];

int nl;

struct Circle{

    double x,r;

    Circle(){}

    Circle(double x,double r):x(x),r(r){}

}C[N];

void addCommonTangent(Circle a,Circle b){

    nl++;

    double sina=(a.r-b.r)/(b.x-a.x);

    double cosa=sqrt(-sina*sina);

    double tana=sina/cosa;

    L[nl].s=Point(a.x+a.r*sina,a.r*cosa);

    L[nl].t=Point(b.x+b.r*sina,b.r*cosa);

    L[nl].k=-tana;

    L[nl].b=L[nl].s.y-L[nl].k*L[nl].s.x;

}

int n;

double alpha,h[N],lb=INF,rb;

inline double F(double x){

    double re=;

    for(int i=;i<=nl;i++) if(x>=L[i].s.x&&x<=L[i].t.x) re=max(re,L[i].f(x));

    for(int i=;i<=n;i++) if(x>=C[i].x-C[i].r&&x<=C[i].x+C[i].r)

        re=max(re,sqrt(C[i].r*C[i].r-(x-C[i].x)*(x-C[i].x)));

    return re;

}

inline double cal(double l,double r){

    return (F(l)+F(r)+*F((l+r)/))*(r-l)/;

}

double simpson(double l,double r,double now){

    double mid=(l+r)/,p=cal(l,mid),q=cal(mid,r);

    if(abs(now-p-q)<eps) return now;

    else return simpson(l,mid,p)+simpson(mid,r,q);

}

Point p;

int main(int argc, const char * argv[]){

    scanf("%d%lf",&n,&alpha);

    for(int i=;i<=n+;i++) scanf("%lf",&h[i]),h[i]+=h[i-];

    for(int i=;i<=n;i++) scanf("%lf",&C[i].r);

    double ta=tan(alpha);

    p=Point(h[n+]/ta,);

    rb=max(rb,p.x);

    {

        C[n].x=h[n]/ta;

        double x=C[n].x,r=C[n].r;

        lb=min(lb,x-r);

        rb=max(rb,x+r);

        if(x+r<p.x){

            double l=r*r/(p.x-x);//she ying ding li

            double h=sqrt(r*r-l*l);

            L[++nl]=Line(Point(x+l,h),p);

        }

    }

    for(int i=n-;i>=;i--){

        C[i].x=h[i]/ta;

        double x=C[i].x,r=C[i].r;

        lb=min(lb,x-r);

        rb=max(rb,x+r);

        if(sgn(C[i+].x-C[i].x-abs(C[i+].r-C[i].r))>)//d-abs(R-r)<=0 nei han

            addCommonTangent(C[i],C[i+]);

    }

    printf("%.2f\n",*simpson(lb,rb,cal(lb,rb)));

    return ;

}

柠檬树