Add Convex Hull Trick

[aftermaaath]

Outline

Introduction

斜率/查詢皆單調

說明斜率優化觀念、使用 deque

• 點不用被 pop
• 點需要被 pop

查詢不單調、斜率單調

使用二分搜

斜率不單調

• 李超線段樹
• 動態凸包
• CDQ

/*
以上每個部分都有：

• 例題
• 提出觀察、列出&整理轉移式
• 時間複雜度、實作細節
• 範例 code
• 總結作法與重點

*/

總結

• 統整各情況、列出思考的步驟

Exercises

• 簡述題目、題解
• https://codeforces.com/contest/1083/problem/E
• https://codeforces.com/contest/311/problem/B
• https://codeforces.com/problemset/problem/319/C
• https://cses.fi/problemset/task/2087
  https://cses.fi/problemset/task/2084
• https://tioj.ck.tp.edu.tw/problems/1676
• https://tioj.ck.tp.edu.tw/problems/1745
• https://codeforces.com/contest/932/problem/F
• https://cses.fi/problemset/task/2085
• https://tioj.ck.tp.edu.tw/problems/1921

References

• Oi wiki - 斜率優化
• TIOJ 建中培訓講義
• Algorithms for competetive programming - Convex hull trick
• [Tutorial] Convex Hull Trick — Geometry being useful
• PEGWiki - Convex hull trick
• USACO Guide - Convex Hull Trick
• https://www.cnblogs.com/Xing-Ling/p/11210179.html

[harry900831]

A problem that may related to this topic: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=3547. It's ICPC World Finals 2011 problem.