杂项
皮克定理
顶点坐标均是整点的简单多边形，其面积 $A$ 和内部格点数目 $i$ 和边上格点数目 $b$ 的关系为 $A=i+\frac{b}{2}-1$。
平面最近点对
问题描述：给出平面上 $n$ 个点，求距离最近的点对。
引理：如果平面上 $n$ 个点的最近点对距离为 $d$，那么将这 $n$ 个点放进 $d\times d$ 的网格中，每个网格中的点数不超过 4。
法一：经典分治算法
- 分：画一条垂直的线将点集均分为左右两个子集。
- 治：分别求出左右两个子集的最近点对。
- 合：求出跨越分界线的最近点对，与子问题的最近点对比较取最优。
令两个子问题中的最近点对距离为 $d$。
找出所有离分界线距离 $d$ 以内的所有点，并按纵坐标（y） 坐标排序。
对每个范围内的点，遍历与其纵坐标（y）之差 d 以内的所有点，更新最近点对。
根据引理，此范围内的点能更新的最近点对是常数级别的。
时间复杂度：$O(n\log n)$
法二：扫描线
对所有点按横坐标（x）排序，从左到右扫描，记录当前的最近点对距离 $d$。
对于一个新的点，遍历之前的点中所有与其横坐标（x）之差小于 d 且纵坐标（y）之差小于 d 的所有点，更新最近点对。
用一个 multiset 存放与新点横坐标（x）之差小于 d 的点，内部按纵坐标（y）排序。
使用队列按 x 坐标顺序入队各点，当队首与新点横坐标（x）之差大于 d 时出队，并且将其从 multiset 中移除。
在 multiset 中二分找到纵坐标（y）之差小于 d 的分界点。
时间复杂度：$O(n\log n)$
法三：随机化算法
令前 $i-1$ 个点的最近点对距离为 $d$，作 $d\times d$ 的网格图，使用哈希表记录每个格子内有哪些点。
对第 $i$ 个点，找到其所在的格子，并找到以此格子为中心的九宫格内的所有点，更新最近点对。
如果最近点对被更新，以新的最近点对距离 $d’$ 重构网格图。
若点的顺序为随机打乱的。那么期望时间复杂度为 $O(n)$。
最小圆覆盖
问题描述：给定平面上 $n$ 个点，求一个半径最小的圆，能覆盖所有的点。
引理：过三个不共线的点可以唯一确定一个圆。
定理：如果点 $p$ 不在点集 S 的最小圆覆盖圆内，那么它一定在 $\lbrace p\rbrace\bigcup S$ 的最小覆盖圆上，即最小覆盖圆一定经过点 $p$。
算法：
1 | 最小圆覆盖（点集 p，边界点集 R） |
时间复杂度：$O(n)$