题意
| F.A.Qs | Home | Discuss | ProblemSet | Status | Ranklist | Contest | 入门OJ | ModifyUser autoint | Logout | 捐赠本站 |
|---|
Problem 1502. -- [NOI2005]月下柠檬树
1502: [NOI2005]月下柠檬树
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1534 Solved: 813
[Submit][Status][Discuss]
Description
李哲非常非常喜欢柠檬树，特别是在静静的夜晚，当天空中有一弯明月温柔地照亮地面上的景物时，他必会悠闲地
坐在他亲手植下的那棵柠檬树旁，独自思索着人生的哲理。李哲是一个喜爱思考的孩子，当他看到在月光的照射下
柠檬树投在地面上的影子是如此的清晰，马上想到了一个问题：树影的面积是多大呢？李哲知道，直接测量面积是
很难的，他想用几何的方法算，因为他对这棵柠檬树的形状了解得非常清楚，而且想好了简化的方法。李哲将整棵
柠檬树分成了n 层，由下向上依次将层编号为1,2,…,n。从第1到n-1 层，每层都是一个圆台型，第n 层(最上面一
层)是圆锥型。对于圆台型，其上下底面都是水平的圆。对于相邻的两个圆台，上层的下底面和下层的上底面重合
。第n 层(最上面一层)圆锥的底面就是第n-1 层圆台的上底面。所有的底面的圆心(包括树顶)处在同一条与地面垂
直的直线上。李哲知道每一层的高度为h1,h2,…,hn，第1 层圆台的下底面距地面的高度为h0，以及每层的下底面
的圆的半径r1,r2,…,rn。李哲用熟知的方法测出了月亮的光线与地面的夹角为alpha。
为了便于计算，假设月亮的光线是平行光，且地面是水平的，在计算时忽略树干所产生的影子。
李哲当然会算了，但是他希望你也来练练手
Input
第1行包含一个整数n和一个实数alpha，表示柠檬树的层数和月亮的光线与地面夹角(单位为弧度)。
第2行包含n+1个实数h0,h1,h2,…,hn，表示树离地的高度和每层的高度。
第3行包含n个实数r1,r2,…,rn，表示柠檬树每层下底面的圆的半径。
上述输入文件中的数据，同一行相邻的两个数之间用一个空格分隔。
输入的所有实数的小数点后可能包含1至10位有效数字。
1≤n≤500，0.3<alpha<π/2，0<hi≤100，0<ri≤100
Output
输出1个实数，表示树影的面积。四舍五入保留两位小数。
Sample Input
2 0.7853981633
10.0 10.00 10.00
4.00 5.00
10.0 10.00 10.00
4.00 5.00
Sample Output
171.97
HINT
Source
[Submit][Status][Discuss]
HOME
分析
参照GFY的题解。
首先，做这题需要知道一点：一个圆从任意一个角度投影都永远是一个圆。
我们可以画出一个简图如下：
如图，这棵树倒影之后，有图中两个圆心p1,p2,他们的横坐标即为这颗树上他们原先的高度乘以cotΘ，而他们的半价却不会变化，因为月光是平行光，所以在圆面与地面平行时，两点间距离不会变化。
如图，倒影最终是圆和他们之间的公切线构成的图形，最右边的点可以看做是半径为eps的圆。之后，可以利用simpson积分公式计算，simpson(l,r)=(f(l)+f(r)+4f(mid))(r-l)/6,若是精度差距大可以继续递归，注意：本题的eps要1e-6以下才能过。
时间复杂度？不知道
代码
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
typedef long long ll;
co double eps=1e-6;
co int N=501;
struct Point{
double x,y;
}s[N],e[N],a[N],b[N];
int n;
il double sqr(double x) {return x*x;}
void cal(Point&s,Point&e,Point a,Point b){
if(fabs(a.y-b.y)<eps) return s=a,e=b,void();
double k=(b.y-a.y)/(b.x-a.x);
s.x=a.x-k*a.y,s.y=sqrt(sqr(a.y)-sqr(a.x-s.x));
e.x=b.x-k*b.y,e.y=sqrt(sqr(b.y)-sqr(b.x-e.x));
// s=(Point){a.x-k*a.y,sqrt(sqr(a.y)-sqr(a.x-s.x))};
// e=(Point){b.x-k*b.y,sqrt(sqr(b.y)-sqr(b.x-e.x))};
}
double f(double x){
double y=0;
for(int i=1;i<=n+1;++i)if(fabs(x-a[i].x)<=a[i].y)
y=std::max(y,sqrt(sqr(a[i].y)-sqr(x-a[i].x)));
for(int i=1;i<=n;++i)if(a[i+1].x-a[i].x-fabs(a[i].y-a[i+1].y)>eps&&s[i].x<=x&&x<=e[i].x)
y=std::max(y,s[i].y+(x-s[i].x)*(e[i].y-s[i].y)/(e[i].x-s[i].x));
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(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
double theta;
scanf("%d%lf",&n,&theta);
theta=1/tan(theta);
double h=0;
for(int i=1;i<=n+1;++i){
scanf("%lf",&a[i].x);
h+=a[i].x,a[i].x=h*theta;
}
for(int i=1;i<=n;++i) scanf("%lf",&a[i].y);
a[n+1].y=a[n+2].y=0;
double L=a[1].x,R=a[n+1].x;
for(int i=1;i<=n;++i){
L=std::min(L,a[i].x-a[i].y),R=std::max(R,a[i].x+a[i].y);
if(a[i+1].x-a[i].x-fabs(a[i+1].y-a[i].y)>eps) // not in
cal(s[i],e[i],a[i],a[i+1]);
}
printf("%.2lf\n",2*simpson(L,R));
return 0;
}