COP3502 Shady Park

Objective

Give practice with Binary Search in C.

Give practice with the math library in C.

Story

You have some semblance of a park, but due to a crazy heat wave, the animals, guests, and employees have all been having health problems. For this problem we will consider the park as a number line. At integral locations of the number line you constructed large, vertical towers with nettings on them to help block the sun. The problem is that when the sun is directly overhead the towers don’t block any of the sun.

You decided that you will change your operation hours, so that for some time during the middle of the day when the towers don’t block as much sun, the park will be closed. The only problem is figuring out at which angle of sun you need to close the park.

Problem

Given the length of the park, location and heights of vertical towers that can block sun rays, and the percentage of the park that must be shaded, determine the starting and ending angle of the sun that causes the park to be too sunny.

Input

Input will begin with a line containing 3 integers, N, L, and P (2 ≤ N ≤ 500,000; 1 ≤ L ≤ 1,000,000,000; 1 ≤ P ≤ 100), representing the number of sun-blocking towers, the length of the park, and the percentage of the park that must be shaded. The following N lines will each contain a description of a sun-blocking tower.

The sun-blocking tower description will consist of 2 space separated integers, x and h (0 ≤ x ≤ L; 1 ≤ h ≤ 1,000,000,000), representing the location from the western most point of the park and the height of the tower respectively. The towers will be given in increasing order of the location. No two towers will have the same location. The first tower will always be at location 0, and the last tower will always be at location L.

Output

Output should contain two space separated floating point values, S and E, representing the starting and ending angles of the sun from the eastern horizon in degrees, respectively. Both values should be rounded to exactly 5 decimal places.

Sample Input
Sample Output





3
5
50
50.19443
146.30993
0
1



4
2



5
1








4
10
25
70.34618
109.65382
0
1



2
3



8
3



10
1









Explanation

Case 1

In the first case the first line (“3 5 50”) says that there are 3 towers, the park is 5 units long, and we need 50% of the park to be shaded.

The second line says that the first tower is at x of 0 (westernmost location of the park). The height of that tower is 1.

The third line says that the second tower is at x of 4 (close to the eastern side of the park). The height of that tower is 2.

The last line says that the third tower is at x of 5 (easternmost location of the park). The height of that tower is also 1.

Here is an image of what the towers might look like at noon. The yellow represents where the sun would fall on the park.
















Note the the East (higher x values) represents the right side of the picture. When the sun is at an angle of 50.19443 we get the following shade.














The last tower covers a range of approximately .833333 units in the park and the second tower covers a range of approximately 1.6666667 units in the park. The first tower (left most) covers a range of 0 units in the park. The combination of all three towers covers a range of 2.5 units which is 50% of the park length.

When the sun is at an angle of 146.30993 we get the following image,


















This is a steeper angle, but this is because the first tower covers a range of 1.5 units in the park and the second tower only covers a range of 1 unit in the park. The third tower covers a range of 0 units in the park.

Case 2

There are 4 towers. The total length of the park is 10. The park needs to be 25% shaded (2.5 units of the park should be covered by shadows).

The first tower is at location 0. It is 1 unit tall

The second tower is at location 2. It is 3 units tall.

The third tower is at location 8. It is also 3 units tall.

The fourth (and final) tower is at location 10. It is 1 unit tall. The towers are symmetric.

When the angle is 70.34618 we get the following image.















The first tower covers 0 units (in the park).

The second tower covers about 1.07143 units.

The third tower covers about 1.07143 units.

The last tower covers about 0.35714 units.

The total coverage is 2.5 units.

When the sun is at an angle of 109.65382, the shaded area is mirrored from that of the original picture. This means that the first tower covers 0.35714 units, but the last tower covers nothing in the park.

Hints

The Sun: Is very far away. All the rays of the sun should be treated as being parallel.

Trigonometry: You need to compute the length of the shadow from the height of a tower and the angle of the sun. The triangle formed is a right triangle. The only values we care about are the legs of the right triangle. We don’t need to know the hypotenuse. You should recall from your trigonometric background that the ratio of the legs is based on the tangent or cotangent of the angle.

Math.h: There is a tangent function built into math.h. To use the tangent function, call the function tan with the angle in radians passed in as the only argument. To use math.h you may need to include -lm (hyphen Lima Michael) at the end of your command line arguments. The lm stands for link math.

Overlapping Shadows: DO NOT double count the sections of the park covered by two towers.

Compute Total SUN Region: I recommend computing the total shaded region of a park when using the sun at a particular angle by computing the sunned region of the park. To do this loop over all the towers in order. I recommend keeping track of the farthest reaching shadow. The amount of sun on the park can be computed based on the location of the “newest” tower and the farthest reaching shadow (excluding the newest tower) when there is a gap. When there is no gap (the farthest reaching tower extends beyond the location of the newest tower) the amount of sun on the park does not need to be updated. Once the amount of sun on the park is updated (or not) the farthest reaching shadow can be updated.

Park Location: Keep in mind that the park starts at location 0 and ends at the park length. Sun or shadows outside that range have no impact on the operation hours.

Grading Criteria

    • Good comments, whitespace, and variable names

        ◦ 15 points

    • No extra input output (e.g. input prompts, “Please enter the number of friends:”)

        ◦ 10 points

    • Consider only good angle (initialized the search area with reasonable angles)

        ◦ 5 points

    • Binary Search over the angle

        ◦ 10 points

    • Determine for a particular angle the total shaded region of the park (use for loop)

        ◦ 5 points

    • Use a math.h function and the angle to find the area covered by any particular tower

        ◦ 5 points

    • Programs will be tested on 10 cases

        ◦ 5 points each

No points will be awarded to programs that do not compile using “gcc -std=gnu11 -lm”. Note the -lm will be useful for this assignment.

Sometimes a requested technique will be given, and solutions without the requested technique will have their maximum points total reduced. For this problem use a binary search. Without this programs will earn at most 50 points!

Any case that causes a program to return a non-zero return code will be treated as wrong. Additionally, any case that takes longer than the maximum allowed time (the max of {5 times my solutions time, 10 seconds}) will also be treated as wrong.

No partial credit will be awarded for an incorrect case.