atcoder#ZONE2021B. 友好の印
友好の印
Score : points
Problem Statement
You are now standing under a very high tower, of height . At a position whose distance from the tower is , there is a UFO up in the sky at height (see the figure at Sample Input / Output 1), and you want to send it a radio wave. There are obstacles between the tower and the UFO. The -th obstacle stands at the position meters from the tower towards the UFO, and has a height of . You want to climb up the tower so that no obstacle crosses the line between you and the UFO. Find the minimum height you need to climb. We assume that the ground is a flat plane, and the towers and obstacles stand vertically from the ground. Additionally, if the top of an obstacle lies exactly on the line connecting you and the UFO, we assume that the obstacle does not cross that line.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer. Your output will be judged as correct when its absolute or relative error from our answer is at most .
1 10 10
3 5
2.857142857142857
If you climb the tower to the height of , no obstacle will cross the line between you and the UFO, as shown below.
1 10 10
3 2
0.0
You can send a radio wave to the UFO without climbing up the tower.
5 896 483
228 59
529 310
339 60
78 266
659 391
245.3080684596577