凸包进阶
凸包二分
判断点是否在凸多边形中
按横坐标（x）二分
按最左和最右的点把凸包分成上凸壳和下凸壳。
通过一次 to-left 测试找出在上半部分还是下半部分。
在对应凸壳上二分找到点在哪两条过相邻的极点的平行 $y$ 轴的竖线之间。
最后与找到的对应极边进行一次 to-left 测试，确定其是否位于凸多边形内。
时间复杂度：$O(\log n)$。
利用极角序二分
从最下方的点出发向其它各点连射线，这些射线方向是按极角序排好的。
通过 to-left 测试与二分查找，可以找出点是在哪两条射线之间。
最后与找到的对应极边进行一次 to-left 测试，确定其是否位于凸多边形内。
时间复杂度：$O(\log n)$。
判断直线是否与凸多边形相交
找到与该直线平行的凸多边形的两条切线，判断该直线是否在两条切线之间。
凸多边形各边对应的向量是按照极角序有序的。
二分查找 前驱和后继 分别以向上和向下穿过直线的切点。
时间复杂度：$O(\log n)$。
过一点求凸多边形切线
存在切线当且仅当点严格在凸包外。
首先 $O(\log n)$ 地判断点是否在凸包外。
切线：切点前后的点在切线同一侧。
对于凸包上一点 $V_i$，如果 $V_{i+1}$ 在射线 $PV_i$ 左侧，则 $V_i$ 点标记为 L，否则标记为 R。
如果 $V_{i-1}$ 的标记与 $V_i$ 不同，则 $V_i$ 是切点。
方法一：上下凸壳
情况一：
点在左极点左侧或右极点右侧。
此时，切点一个在上凸壳，一个在下凸壳。
上下凸壳的序列都满足 LLL...RRR... 或 RRR...RRR...，各自二分即可。
情况二：
两个切点均在上凸壳或下凸壳
以上凸壳为例，此时的序列为：LLL...LLLRRR...RRRLLL...LLL
二分找到横坐标（x）离该点最近的点，然后将上凸壳分为两部分，这两部分又可以各自二分找到切点。
方法二：射线划分
点向凸多边形上任意一点作射线，将凸多边形分为左右部分。
在两部分上分别二分即可。
时间复杂度：$O(\log n)$。
方法三：射线划分$\cdot$改
以找到最左侧的切线为例。
情况一：
序列中第一个点是 R，则序列形如 RRR...RRRLLL...LLLRRR...RRR
如果把最开始的几个 R 视作 L，那么序列则转化为可以二分的形式，并且可以二分找到切点。
最开始的几个 R 一定在第一条切线的右侧。
情况二：
序列中第一个点是 L，则序列形如 LLL...LLLRRR...RRRLLL...LLL。
如果把最后的几个 L 视作 R，那么序列则转化为可以二分的形式，并且可以二分找到切点。
最后的几个 L 一定在第一条切线的右侧。
时间复杂度：$O(\log n)$。
动态凸包
增量法求凸包，根据已有知识，可以做到 $O(n^2)$。
维护一个数据结构，支持以下两个操作
- 修改：往当前点集中加入一点。
- 询问：查询一点是否在当前点集的凸包内。
以按横坐标（x）维护上凸壳为例，即 set 中的点按横坐标（x）维护。
- 询问，使用前文 $O(\log n)$ 判断点是否在凸包内的做法即可。
- 修改，二分找到横坐标（x）最近的点，然后分别向左向右遍历各点找切线，对于找到切线前的点将其删除。
特殊情况：点在凸包左极点左侧。
考虑一条切线即可，另一个切线在下凸壳考虑。
时间复杂度：$O(n\log n)$。
极角序维护方式同理。
闵可夫斯基和
$A+B=\lbrace \vec a+\vec b\mid \vec a\in A,\vec b\in B \rbrace$
性质：原凸边形的一条极边对应闵可夫斯基和的一条极边。
求闵可夫斯基和
对两个凸多边形的所有边按极角排序。
确定起点，然后依次加入各边即可。
特殊情况：三点共线。
求两个凸多边形之间的最大/小距离
令两个凸多边形对应的点集分别为 $A$ 和 $B$。
$A-B=A+(-B)=\lbrace\vec a-\vec b\mid \vec a\in A,\vec b\in B \rbrace$
它们之间的最大/小距离是所有 $\vec a-\vec b$ 中长度最大/小的。
求出闵可夫斯基和，找到离原点最远/近的点即可。
时间复杂度：$O(n)$。