National Olympiad in Informatics, China, 2005

Day 2, Problem 3 - Lemon Tree Under the Moon

Li Zhe really really likes his lemon tree, especially in silent nights. When the sky has a crescent moon gently casting a light onto the scenery on earth, he feels the need to sit leisurely under the lemon tree which he had planted with his own hands, pondering the philosophies of life.

Li Zhe is a child who enjoys thinking. When he noticed that the shadow casted by the moonlight hitting the lemon tree is extra clear on the ground, he immediately comes up with a question: how large is the area of the tree's shadow?

Li Zhe knows that it is very difficult to directly measure area. Since he is very familiar with the shape of the lemon tree, he would like to use a geometrical method to calculate it. Thus, he has come up with a simplified method.

Li Zhe has split the entire lemon tree into n layers, labeled 1, 2, …, n from bottom to top. From layer 1 to layer n-1, each layer is disk-shaped (*), with the exception of layer n (the uppermost layer), which is conical. Regarding the disks, the upper and lower surfaces are parallel to each other. Regarding any two neighboring disks, the bottom surface of the upper disk is always completely touching the top surface of the lower disk, and vice versa. The bottom surface of the cone at layer n (the uppermost layer) is the top surface of the disk at layer n-1. The circular centers of all of the surfaces (including the tree top) are aligned along a straight line that is perpendicular to the ground. Li Zhe knows that the heights of all the layers are h₁, h₂, …, h_n, that the distance from the bottom surface of layer 1 to the ground is h₀, and that the radius of the bottom surface of each layer is r₁, r₂, …, r_n. Li Zhe has used a familiar method to determine the angle alpha of the moonlight's rays against the surface of the ground.

Figure 1. Cross-section of the lemon tree

Figure 2. Depiction of moonlight ray angles

To simplify calculations, assume that light rays are parallel to each other, the ground is perfectly level, and the area of the shadow produced by the tree trunk is negligible. Li Zhe obviously knows how to find the answer, but he wishes for you to also try your hands.

Input Format

Line 1 of input contains the integer n and the real number alpha, representing the number of layers in the lemon tree and the angle with which the moonlight strikes the ground.
Line 2 contains n+1 real numbers h₀, h₁, h₂, …, h_n, representing the heights of all the layers.
Line 3 contains n real numbers r₁, r₂, …, r_n, representing the radii of the bottom surfaces of all the layers.
Adjacent values on the same line in the input will always be separated by a single space.
Real values in the input will have between 1 and 10 significant digits, inclusive.

Output Format

The output should contain 1 real number - the area of the tree's shadow, rounded and displayed to two places after the decimal.

Sample Input

2 0.7853981633
10.0 10.00 10.00
4.00 5.00

Sample Output

171.97

Constraints

1 ≤ n ≤ 500; 0.3 < alpha < π/2; 0 < h_i ≤ 100; 0 < r_i ≤ 100.
In test cases worth 10% of points, n = 1.
In test cases worth 30% of points, n ≤ 2.
In test cases worth 60% of points, n ≤ 20.
In test cases worth 100% of points, n ≤ 500.

* Note from translator: Layers 1 to n-1 are more accurately described as truncated cone-shaped.

All Submissions
Best Solutions

Point Value: 50 (partial)
Time Limit: 0.25s
Memory Limit: 256M
Added: Jun 02, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)