Given the length of the park, location and heights of vertical towers that can block sun rays

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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.

 

Attachments:

Expert's Answer

691 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of