皮克定理

​顶点坐标均是整数的简单多边形，其面积 $A$ 和内部格点数目 $i$ 和边上格点数目 $b$ 的关系为 $A=i+\frac{b}{2}-1$。

平面最近点对

​问题描述：给出平面上 $n$ 个点，求距离最近的点对。以下假设 $n\ge 2$；一旦发现两个点坐标完全相同，应立即返回 $0$。

​引理：如果平面上 $n$ 个点的最近点对距离为 $d>0$，那么将这些点放进边长为 $d$ 的半开网格中，每个格子内的点数不超过 $4$。

法一：经典分治算法

• 预处理：将所有点按横坐标排序；
• 分：按排序下标将点集均分为左右两个子集；
• 治：分别求出左右两个子集的最近点对距离 $d_l,d_r$；
• 合：令 $d=min(d_l,d_r)$，求出跨越分界线且距离小于 $d$ 的点对。

​为了得到 $O(n\log n)$ 的复杂度，递归返回时还应将左右两部分按纵坐标线性归并。然后从这个有序序列中筛出横坐标到分界线距离小于 $d$ 的点；条带已经按纵坐标有序，每个点只需检查其后纵坐标之差小于 $d$ 的常数个点，标准结论为至多 $7$ 个。

​这样每一递归层的归并和条带扫描总计 $O(n)$，递推式为 $T(n)=2T(n/2)+O(n)$，总时间复杂度为 $O(n\log n)$。若在每个递归结点重新将条带按纵坐标排序，则总时间复杂度会变为 $O(n{\log }^{2}n)$。

法二：扫描线

​对所有点按横坐标（x）排序，从左到右扫描，记录当前的最近点对距离 $d$。

​对于一个新的点，遍历之前的点中所有与其横坐标（x）之差小于 $d$ 且纵坐标（y）之差小于 $d$ 的所有点，更新最近点对。

​用一个 multiset 存放与新点横坐标（x）之差小于 $d$ 的点，内部按纵坐标（y）排序。

​使用队列按 $x$ 坐标顺序入队各点，当队首与新点横坐标（x）之差大于等于 $d$ 时出队，并且将其从 multiset 中移除。

​在 multiset 中二分找到纵坐标（y）之差小于 $d$ 的分界点。

​时间复杂度：$O(n\log n)$。

法三：随机化算法

​先将点均匀随机打乱，用前两个点的距离初始化 $d$；若两点重合则直接返回 $0$。令前 $i-1$ 个点的最近点对距离为 $d>0$，作 $d\times d$ 的半开网格，使用哈希表记录每个格子内有哪些点。格子编号应使用 $(\lfloor x/d\rfloor ,\lfloor y/d\rfloor )$；坐标为负数时，不能用向零截断的整数除法代替下取整。

​对第 $i$ 个点，找到其所在的格子，并找到以此格子为中心的九宫格内的所有点，更新最近点对。

​如果最近点对被更新且 $d^{\prime }>0$，以新的距离 $d^{\prime }$ 重构网格。若发现重复点使 $d^{\prime }=0$，应在除法或重构网格之前立即返回 $0$。

​在随机排列独立于输入、哈希表操作期望为 $O(1)$ 的前提下，该算法的期望时间复杂度为 $O(n)$。任意固定或对抗性的插入顺序不保证线性复杂度，最坏可以达到 $O(n^2)$。

辛普森积分

普通辛普森积分

​辛普森积分简单来说就是使用二次函数去拟合待求曲线。

​对于一个二次函数 $f(x)=a{x}^2+bx+c$，有

$${\int }_l^{r}f(x)dx={\displaystyle \frac{r-l}{6}}(f(l)+4f\left({\displaystyle \frac{l+r}{2}}\right)+f(r))$$

​对于一个曲线 $g(x)$，若其积分区间为 $[l,r]$，将 $[l,r]$ 均分成 $2n$ 个区间，其中第 $i$ 个区间为 $[x_i,x_{i+1}],x_i=l+ih,h=\frac{r-l}{2n}$。

​对于两个相邻的区间，三个点 $(x_i,g(x_i)),(x_{i+1},g(x_{i+1})),(x_{i+2},g(x_{i+2}))$ 拟合成一段二次函数，套用二次函数积分公式即可。

自适应辛普森积分

​对于普通辛普森积分，若 $n$ 取太小，无法保证拟合精度；而若 $n$ 取太大，无法保证时间。

​所以可以采用自适应辛普森积分。

​记 $S=S(l,r)$ 为当前区间的一次辛普森估计，$m=(l+r)/2$，并令

$$S_2=S(l,m)+S(m,r)$$

​$S_2-S$ 并不是真实误差。只有在被积函数足够光滑、误差已经进入相应渐近区间时，Richardson 外推才给出

$$I-S_2\approx {\displaystyle \frac{S_2-S}{15}}$$

​因此，要求当前区间的绝对误差不超过 $\epsilon$ 时，通常以

$$|S_2-S|\le 15\epsilon$$

​作为接受条件，并返回校正后的结果

$$S_2+{\displaystyle \frac{S_2-S}{15}}$$

​若不满足条件，则分别以 $\epsilon /2$ 递归处理 $[l,m]$ 和 $[m,r]$。强制细分最少层数只能降低误差偶然抵消的风险，不能替代终止保护；实现还必须设置最大递归深度，并在浮点中点已经等于端点时停止。达到这些上限时，只能返回当前近似或报告未达到目标精度，不能继续承诺 $\epsilon$ 误差界。

​已知不连续点应预先作为分界，将原区间拆成若干子区间分别积分；若函数在分界点无定义，还应使用单侧极限或避免在该点直接求值。端点奇异、无穷区间等瑕积分需要极限、截断或变量代换，不能仅依靠继续二分。算法没有只由 $\epsilon$ 决定的统一复杂度；若实际访问 $K$ 个递归结点、单次函数求值代价为 $T_f$，则可记为 $O(K{T}_f)$，其中 $K$ 取决于函数性质和误差要求。

仿射变换

仿射变换将点映射为 $P\mapsto AP+b$，其中 $A$ 是线性变换，$b$ 是平移。讨论椭圆与圆、平行四边形与正方形之间的可逆变换时，需要假设 $A$ 可逆。

应用

椭圆 $\stackrel{\text{可逆仿射变换}}{\iff }$ 圆

在主轴方向已经对应平行的常见情形下，同一个仿射变换能将多个椭圆分别变成圆，当且仅当它们的长短轴比例相同，即离心率相同。

平行四边形 $\stackrel{\text{可逆仿射变换}}{\iff }$ 正方形

任意一个非退化平行四边形都能通过可逆仿射变换变成正方形。对于多个非退化平行四边形，设第 $i$ 个的一组相邻边向量为 $u_i,v_i$，并记边矩阵

$$M_i=[u_i{v}_i]$$

同一个仿射变换能将它们分别变成正方形，所得正方形不要求同大小、同位置或同朝向。当且仅当任选一个 $M_1$ 后，对每个 $i$ 都存在 ${\lambda }_i>0$ 和正交矩阵 $R_i$（即 $R_i^{\mathsf{T}}{R}_i=I$），使

$$M_1^{-1}{M}_i={\lambda }_i{R}_i$$

平移 $b$ 不影响这个形状条件。特别地，若所有平行四边形的两组对应边已经分别平行，则还必须保证 $\Vert u_i\Vert /\Vert v_i\Vert$ 对所有 $i$ 相同。仅有“底角相等、底边平行”并不充分：单位正方形和边长为 $2,1$ 的矩形满足这两个条件，却不可能被同一个可逆仿射变换同时变成正方形。

仿射变换将面积统一乘以 $|detA|$。

例如，当 $a,b>0$ 时，$(x,y)\mapsto (x/a,y/b)$ 对应的面积变化为 $S\mapsto S/(ab)$。