答えは \(i<j\) について \((X_i,H_i),(X_j,H_j)\) を通る直線の切片、つまり　\(\displaystyle \frac{H_iX_j-H_jX_i}{X_j-X_i}\) の取りうる最大値となります。

この値を \(M\) とすると

\(\displaystyle \frac{H_iX_j-H_jX_i}{X_j-X_i}\leq M\)

\(\displaystyle H_iX_j-H_jX_i\leq MX_j-MX_i\)

\(\displaystyle (H_i-M)X_j\leq (H_j-M)X_i\)

\(\displaystyle \frac{H_i-M}{X_i}\leq \frac{H_j-M}{X_j}\)

ゆえに、\(\displaystyle \frac{H_i-M}{X_i}\) が昇順に並んでいることと同値なので、隣接する項についてのみ考えればよいため、答えは \(\displaystyle \frac{H_iX_{i+1}-H_{i+1}X_i}{X_{i+1}-X_i}\) の取りうる最大値となり、これは \(O(N)\) で求めることができます。

（ なお、全ての \(i\) について \(H_iX_{i+1}-H_{i+1}X_i< 0\) なら答えは \(-1\) となります。)

実装例 ( PyPy )