かわぐちさんのCHT(Convex hull trick)

かわぐちさんのCHT(Convex hull trick)

1. 十分低いxで、yの値が一番高い直線を見付ける
2. それをxの値を増やしながらある範囲の全てのxにおいて見付ける。傾きが変化した場所も分かるので、交点も見付かる。一番上の直線以外を全部捨てる。
3. 事前の計算終了。後はxに応じて出力する。