/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
ストーリー
まずは友好の印として、UFO の操縦プログラムをクラッシュさせてみよう。俺は机の上の ZONe 缶に偽装した USB から、地球最強のコンピュータウイルス「KARATE」を取り出した。
こいつを UFO に送りつけてやる。UFO がどんなシステムを使っているかは分からないが、あらゆるシステムをクラッシュさせてきた KARATE は、きっと効くはずだ。
問題文
あなたは今、高さ 1000 の非常に高いタワーの下にいます。タワーから距離 D 離れた位置の上空 H の高さに UFO がおり（入出力例 1 の図を参照してください）、あなたは UFO に電波を届けたいです。
タワーと UFO の間には遮蔽物が N 個あります。i 番目の遮蔽物はタワーから UFO の方向に向かって距離 d_i の場所に位置していて、高さは h_i です。
あなたはタワーを上って、あなたと UFO の間の直線上に遮蔽物が 1 つも無い状態にしたいです。上る必要のある最低の高さを求めてください。
なお、地面は凹凸のない水平面であり、タワー及び遮蔽物は地面と垂直に建っているものとします。
また、あなたと UFO の間の直線上にちょうど遮蔽物の上端があるとき、その遮蔽物には遮蔽されていないものとします。
制約
- 入力は全て整数
- 1 ≤ N ≤ 100
- 1 ≤ d_i < D ≤ 1000
- 1 ≤ h_i < H ≤ 1000
入力
入力は以下の形式で標準入力から与えられる。
N D H d_1 h_1 d_2 h_2 \vdots d_N h_N
出力
答えを出力せよ。
想定解答との絶対誤差または相対誤差が 10^{-3} 以下であれば正解と判定される。
入力例 1
1 10 10 3 5
出力例 1
2.857142857142857
タワーを \frac{20}{7} 上ると、図のようにあなたと UFO の間の直線上に遮蔽物が 1 つも無い状態になります。
入力例 2
1 10 10 3 2
出力例 2
0.0
タワーを登らずとも UFO に電波を届けることができます。
入力例 3
5 896 483 228 59 529 310 339 60 78 266 659 391
出力例 3
245.3080684596577
Score : 200 points
Problem Statement
You are now standing under a very high tower, of height 1000. At a position whose distance from the tower is D, there is a UFO up in the sky at height H (see the figure at Sample Input / Output 1), and you want to send it a radio wave.
There are N obstacles between the tower and the UFO. The i-th obstacle stands at the position d_i meters from the tower towards the UFO, and has a height of h_i.
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.
- 1 ≤ N ≤ 100
- 1 ≤ d_i < D ≤ 1000
- 1 ≤ h_i < H ≤ 1000
Input
Input is given from Standard Input in the following format:
N D H d_1 h_1 d_2 h_2 \vdots d_N h_N
Output
Print the answer.
Your output will be judged as correct when its absolute or relative error from our answer is at most 10^{-3}.
Sample Input 1
1 10 10 3 5
Sample Output 1
2.857142857142857
If you climb the tower to the height of \frac{20}{7}, no obstacle will cross the line between you and the UFO, as shown below.
Sample Input 2
1 10 10 3 2
Sample Output 2
0.0
You can send a radio wave to the UFO without climbing up the tower.
Sample Input 3
5 896 483 228 59 529 310 339 60 78 266 659 391
Sample Output 3
245.3080684596577