NOI '05 P6 - Lemon Tree Under the Moon

View as PDF

Submit solution

Points: 30
Time limit: 0.18s
Memory limit: 256M

Problem types
National Olympiad in Informatics, China, 2005

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, \ldots, 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_{1}, h_{2}, \ldots, h_{n}, that the distance from the bottom surface of layer 1 to the ground is h_{0}, and that the radius of the bottom surface of each layer is r_{1}, r_{2}, \ldots, 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 Specification

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_{0}, h_{1}, h_{2}, \ldots, h_{n}, representing the heights of all the layers.
Line 3 contains n real numbers r_{1}, r_{2}, \ldots, 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 Specification

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



1 \le n \le500; 0.3 < alpha < \frac{\pi}{2}; 0 < h_{i} \le 100; 0 < r_{i} \le 100.
In test cases worth 10\% of points, n \le 1.
In test cases worth 30\% of points, n \le 2.
In test cases worth 60\% of points, n \le 20.
In test cases worth 100\% of points, n \le 500.

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

Problem translated to English by Alex.


  • 1
    Alb11747  commented on Sept. 25, 2020, 4:42 p.m.

    What am I missing from my program? Is my angle calculation correct?

    • 0
      Render_Main  commented on Sept. 25, 2020, 6:55 p.m. edit 2

      Your program handles the angle correctly. You did wrong in the area calculation.

      Each (except the last) layer of the tree is truncated cone-shaped. A possible shape of the tree's shadow may look like this:

      this will not appear in any test cases

      To solve this problem, you need to find the area of the shaded region, which can be done analytically using the scan-line algorithm or using a numerical integration method like the Simpson's rule. The implementation is left as an exercise for you.

      Edit 2021-01-30: additional test cases are added to the problem and numerical solutions no longer pass.

      • 0
        Alb11747  commented on Oct. 2, 2020, 11:33 p.m.

        Is the problem accuracy now or am I just completely off?