皮克定理

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

平面最近点对

​问题描述：给出平面上 $n$ 个点，求距离最近的点对。

​引理：如果平面上 $n$ 个点的最近点对距离为 $d$，那么将这 $n$ 个点放进 $d\times d$ 的网格中，每个网格中的点数不超过 $4$。

法一：经典分治算法

• 分：画一条垂直的线将点集均分为左右两个子集
• 治：分别求出左右两个子集的最近点对
• 合：求出跨越分界线的最近点对，与子问题的最近点对比较取最优

​令两个子问题的最近点对距离为 $d$。

​找出所有离分界线距离 $d$ 以内的所有点，并按纵坐标（y）排序。

​对每个范围内的点，遍历与其纵坐标（y）之差 d 以内的所有点，更新最近点对。

​根据引理，此范围内的点能更新的最近点对是常数级别的。

法二：扫描线

​对所有点按横坐标（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^{\prime }$ 重构网格图。

​若点的顺序为随机打乱的，那么期望时间复杂度为 $O(n)$。

辛普森积分

普通辛普森积分

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

​对于一个二次函数 $f(x)=a{x}^2+bx+c$，${\int }_l^{r}f(i)dx={\displaystyle \frac{(r-l)(f(l)+f(r)+4f(\frac{l+r}{2}))}{6}}$

​对于一个曲线 $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$ 取太大，无法保证时间。

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

​自适应辛普森积分采用分治的方式，若将当前区间再递归一层后计算的答案和当前直接计算的答案误差小于 $eps$，则视作正确，停止递归。

​在分治判断的时候，除了判断精度是否正确，一般还要强制执行最少的迭代次数。

注：辛普森积分需要注意积分区间的连续性，如果中间存在间断部分，使用辛普森积分求解可能会出现错误。

仿射变换

仿射变换指，对点进行变换：$P\to AP+b$，其中 $A$ 是线性变换（旋转、缩放、剪切），$b$ 是平移。

应用

椭圆 $\stackrel{\mathrm{仿}\mathrm{射}\mathrm{变}\mathrm{换}}{\iff }$ 圆

对多个椭圆同时进行仿射变换成圆，需要满足离心率相等和主轴方向平行。

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

对多个平行四边形同时进行仿射变换成正方形，需要满足底角相等，底边平行。

仿射变换面积等比例变换

$(x,y)\to (\frac{x}{a},\frac{y}{b})$，$S\to \frac{S}{ab}$