二维计算几何基础
点、向量、直线
点：\((x,y)\) .
向量：\((x,y)\) .
向量的运算（\(A=(a_1,a_2),\ B=(b_1,b_2)\)）：
-
加减：\(A\pm B=(a_1\pm b_1,a_2\pm b_2)\)
-
数乘：\(k\cdot A=(k\cdot a_1,k\cdot a_2)\)
-
模长：\(|A|=\sqrt{a_1^2+a_2^2}\) .
-
幅角：\(\theta=\arctan\frac{a_2}{a_1}\)（可以用
atan2求）.因为是 \(\tan\theta=\frac{a_2}{a_1}\)，所以一般情况极角排序（按幅角排序）可以用斜率排 .
-
点积：\(A\cdot B=a_1b_1+a_2b_2=|A|\cdot |B|\cdot\cos\theta\) .
判断夹角：\(A\cdot B>0\) 锐角，\(A\cdot B=0\) 直角，\(A\cdot B<0\) 钝角 .
-
叉积：\(A\times B=a_1b_2-b_1a_2=|A|\cdot |B|\cdot\sin\theta\)（有向面积）.
可以看成行列式：\(A\times B=\begin{vmatrix}a_1&a_2\\b_1&b_2\end{vmatrix}\) .
判断方向：\(A\cdot B>0\) 逆时针，\(A\cdot B=0\) 共线，\(A\cdot B<0\) 顺时针 .
-
旋转：\((a_1,a_2)\) 转 \(\theta\)：\((a_1\cos\theta-a_2\sin\theta,a_1\sin\theta+a_2\cos\theta)\) .
直线：记两个点 \(A,B\)，那么如果向量 \(\bm v=B-A\)，直线上的点就可以表为 \(A+\bm vt\)，限制 \(t\) 可以得到线段或射线 .
点到直线的距离：
- 文化课知识：\(P(x_0,y_0),\ \ell:ax+by+c=0\)，距离：\[\operatorname{dist}(P,\ell)=\dfrac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}} \]
- 叉积算出平行四边形面积然后除以底 .
线段相交：
- 跨立实验：两端点在另一条直线的两侧（叉积判断）.
- 需要特殊处理共线情况 .
求交点：解方程 .
特殊情况（三点共线、四点共圆）在某些情形下可以直接扰动解决 .
POJ 3304 Segments
给 \(n\) 条线段，问有没有一条直线，满足这些线段在直线上的投影有公共点 .
\(n\le 100\) .
Solution
考虑找一条过所有线段的直线然后画一条与其垂直的线就好了 .
只需要连每两个线段端点然后判断即可找到一条过所有线段的直线 .
需要特判 \(n=1\) .
时间复杂度 \(O(n^3)\) .
POJ 2826 An Easy Problem?!
给两块长度相等的板子，天上垂直落下雨滴，问最后接到多少水 .
Solution
就是找到线段最高点连一下算三角形面积，有一个重要边界情况需要特殊处理：
多边形基础
多边形：用顶点表示 .
简单多边形面积：三角剖分，答案等于相邻边叉积和的一半 .
简单多边形重心：三角剖分，三角形是平凡的，然后合并就行了 .
点和多边形的位置关系（PIP）：从点出发引一条射线，判断交点奇偶性，可能需要多引几条规避边界问题 .
凸包
凸包就是最小的包含所有给定点的凸多边形 .
\([0,n]^2\) 上整点凸包点数上界：\(O(n^{2/3})\)，证明细节可参考杨景钦 2017 年集训队论文 .
Andrew 算法
单调栈处理即可 .
详细说明 .
动态凸包
动态凸包：带插入删除维护凸包信息 .
每次插入只会改 \(O(1)\) 个点，删除必须先插入，所以维护凸包的结构复杂度均摊下来是没有问题的 . 只需要用平衡树状物维护上下凸壳就可以了 .
练习题（板子）：
半平面交
半平面：一条直线一侧的位置 .
凸包和半平面交是对偶问题，所以做法也是基本相似的 . S&I 算法：极角排序后单调栈维护 .
HNOI2012 射箭
有若 \(n\) 条竖着的线段 \(x=x_0,\ y\in[y_1,y_2]\) 组成序列 \(\{a\}\)，画一个过原点的抛物线问过的线段和线段序列 \(\{a\}\) 的 LCP 最长是多少 .
\(n\le 10^5\) .
Solution
起手二分，那么一条抛物线 \(y=ax^2+bx\) 过 \(x=x_0,\ y\in[y_1,y_2]\) 当且仅当：
不等号两个方向分别是一个半平面，跑半平面交判断即可 .
Minkowski 和
定义：两个凸包 \(A,B\) 的 Minkowski 和 \(C=\{a+b\mid a\in A,b\in B\}\) .
就是相当于对于凸包 \(A\) 沿着 \(B\) 的每个向量移动后得到的所有位置的并 .
做法不是很困难，极角排序后归并就行了 . 如果有三点共线情况还需要再求一次凸包 .
JSOI2018 战争
给两个凸多边形 \(A,B\)，若干次操作，每次将 \(B\) 平移一下，操作后问 \(A,B\) 是否有交 .
\(A,B\) 的点数和操作次数均不大于 \(10^5\) .
Solution
设 \(A,B\) 上有点 \(a,b\)，那么移动向量 \(\bm v\) 满足有交当且仅当存在 \(b+\bm v=a\) .
可以写成 \(\bm v=a-b\)，Minkowski 和算 \(A+(-B)\) 就行了 .
杂项
三维计算几何部分我就不写了 .
Pick 定理
顶点均为整点的简单多边形，面积 \(A\)、内部格点数和边上格点数满足 \(A=i+\frac b2-1\) .
最小圆覆盖
最小圆覆盖：平面上若干个点，找一个最小的圆包含所有点 .
暴力：枚举三个点 \(i,j,k\) 组成一个圆，两个点 \(i,j\) 作为直径组成一个圆 .
优化：目前枚举到的点不能在最优圆内 .
然后随机打乱复杂度就对了 .
平面最近点对
cdq 分治双指针，复杂度是 \(O(n\log n)\) 或者 \(O(n\log^2n)\) 的 .
关于复杂度可以发现的是某个点周围有用的点不会很多：
