Convex Hull Trick のまとめ
二次元平面上に直線$ y=a_ix+b_iがたくさんある。$ xが与えられた時$ yが最大でいくつになるか/最小でいくつになるかをもとめる!
直線を追加するクエリと、与えられたxで最大または最小値を取るような直線の値を求める
追加する直線が傾きについて単調増加/単調減少だとdequeやvectorでよい(末尾比較だけで済むので)
そうでないときはmapを使って、傾きが近いやつと比較して、要らない方を消す
判定方法は自分の周りの傾きが近い2つの交点より上を自分が通るかどうか
例題
この問題の場合、直線の傾きが小さい順に追加できるので実装は難しくない。難しくない...?