Convex Hull Trick のまとめ
#Convex Hull Trick #高度典型 #数学#データ構造
二次元平面上に直線$ y=a_ix+b_iがたくさんある。$ xが与えられた時$ yが最大でいくつになるか/最小でいくつになるかをもとめる!
参考記事1
参考記事2
えびちゃんさんのスライド 詳しい 図つきでわかりやすい(最小値をとる直線の傾きは単調減少、が理解しやすい)
直線を追加するクエリと、与えられたxで最大または最小値を取るような直線の値を求める
追加する直線が傾きについて単調増加/単調減少だとdequeやvectorでよい(末尾比較だけで済むので)
そうでないときはmapを使って、傾きが近いやつと比較して、要らない方を消す
判定方法は自分の周りの傾きが近い2つの交点より上を自分が通るかどうか
例題
G - Shopping in AtCoder store
提出コード
この問題の場合、直線の傾きが小さい順に追加できるので実装は難しくない。難しくない...?