/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
1 から N の番号がついた N 棟のビルが数直線上に建っています。
ビル i は座標 X_i にあり、高さは H_i です。ビルの高さ方向以外の大きさは無視できるものとします。
座標 x の高さ h の地点 P からビル i が見えるとは、ビル i 上のある点 Q であって、線分 PQ が他のビルと共有点を持たないものが存在することと定めます。
座標 0 から全てのビルを見ることができない高さの最大値を求めてください。ただし、高さは非負の値を取るとし、高さ 0 で全てのビルを見ることができる場合はかわりに -1 と答えてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq X_1 < \dots < X_N \leq 10^9
- 1 \leq H_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N X_1 H_1 \vdots X_N H_N
出力
座標 0、高さ 0 の地点から全てのビルを見ることができる場合は -1 と出力せよ。
そうでないとき、座標 0 から全てのビルを見ることができない高さの最大値を出力せよ。真の解との絶対誤差または相対誤差が 10^{-9} 以下のとき正解と判定される。
入力例 1
3 3 2 5 4 7 5
出力例 1
1.500000000000000000
座標 0 高さ 1.5 の位置ではビル 3 を見ることができません。高さが 1.5 より僅かでも高ければビル 3 を含む全てのビルを見ることができるため、答えは 1.5 です。
入力例 2
2 1 1 2 100
出力例 2
-1
-1.000 などの出力では不正解となることに注意してください。
入力例 3
3 1 1 2 2 3 3
出力例 3
0.000000000000000000
入力例 4
4 10 10 17 5 20 100 27 270
出力例 4
17.142857142857142350
Score : 525 points
Problem Statement
There are N buildings numbered 1 to N on a number line.
Building i is at coordinate X_i and has height H_i. The size in directions other than height is negligible.
From a point P with coordinate x and height h, building i is considered visible if there exists a point Q on building i such that the line segment PQ does not intersect with any other building.
Find the maximum height at coordinate 0 from which it is not possible to see all buildings. Height must be non-negative; if it is possible to see all buildings at height 0 at coordinate 0, report -1 instead.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq X_1 < \dots < X_N \leq 10^9
- 1 \leq H_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X_1 H_1 \vdots X_N H_N
Output
If it is possible to see all buildings from coordinate 0 and height 0, print -1. Otherwise, print the maximum height at coordinate 0 from which it is not possible to see all buildings. Answers with an absolute or relative error of at most 10^{-9} from the true answer will be considered correct.
Sample Input 1
3 3 2 5 4 7 5
Sample Output 1
1.500000000000000000
From coordinate 0 and height 1.5, building 3 cannot be seen. If the height is even slightly greater than 1.5, all buildings including building 3 can be seen. Thus, the answer is 1.5.
Sample Input 2
2 1 1 2 100
Sample Output 2
-1
Note that -1.000 or similar outputs would be considered incorrect.
Sample Input 3
3 1 1 2 2 3 3
Sample Output 3
0.000000000000000000
Sample Input 4
4 10 10 17 5 20 100 27 270
Sample Output 4
17.142857142857142350