题意

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

Sample Output

171.97

HINT

Source

[Submit][Status][Discuss]

HOME
Back

한국어
中文
فارسی
English
ไทย

Based on opensource project hustoj.

分析

参照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;

}

巴特西

[NOI2005]月下柠檬树

题意