好用的参考：来自俊杰哥哥的板子
二维基础
特殊值与精度
- 无穷 $1.0/0.0=\operatorname{INFINITY},1.0/0.0=\operatorname{-INFINITY}$
- 非数 $0.0/0.0 =\operatorname{NAN}$
- 要注意，$\operatorname{NAN} (\ge,\le,>,<,= ) x$ 结果均为 False，只有 $\operatorname{NAN} \neq x$ 结果才为 True
- $+0.0,-0.0$ 也是一类特殊值，因而我们在比较时需要加入容限 eps。
- 特别的，频繁使用数学函数（开方，三角函数）等容易造成精度丢失，尽量减少使用。
点与向量
点的定义方法：struct Point {double x,y;};
向量的定义方法：using Vector=Point;（直接使用 Point 亦可）
- 向量点积: $\vec{a}\cdot\vec{b}=a_xb_x+a_yb_y$
- 几何意义：$\vec{a} \cdot \vec{b} = \left | \vec{a} \right | \left | \vec{b} \right | \cos \theta$
- 向量的长度：$|\vec{a}| = \sqrt{\vec{a} \cdot \vec{a} }$
- 向量的夹角：$\cos\theta=\frac{\vec{a}\cdot\vec{b}}{|\vec{a}||\vec{b}|}$
- 向量的投影：$|\vec{a}|\cos\theta=\frac{\vec{a}\cdot\vec{b}}{|\vec{b}|}$
- 向量垂直：$\vec{a} \cdot \vec{b} = 0$
- 向量叉积：$\vec{a}\times\vec{b}=(a_xb_y-a_yb_x)\widehat{k}$
注：$\widehat{k}$ 表示 $\vec{k}$ 是一个单位向量。
- 几何意义$:\vec{a}\times\vec{b}=|\vec{a}|\left|\vec{b}\right|\sin\theta\widehat{k}$
平行四边形面积：$|\vec{a}||\vec{b}||\sin\theta|=|\vec{a}\times\vec{b}|$
向量平行：$\vec{a} \times \vec{b} = \vec{0}$
to-left 测试判断点 $P$ 在有向直线 $AB$ 左侧/右侧/上
- $\begin{cases}\overrightarrow{AB}\times\overrightarrow{AP}>0,&P\text{在有向直线}AB\text{左侧}\newline\overrightarrow{AB}\times\overrightarrow{AP}<0,&P\text{在有向直线}AB\text{右侧}\newline\overrightarrow{AB}\times\overrightarrow{AP}=0,&P\text{在有向直线}AB\text{上}\end{cases}$
- 向量 $\vec{a}$ 逆时针旋转 $\theta$
- $\begin{bmatrix}\cos\theta&-\sin\theta\\sin\theta&\cos\theta\end{bmatrix}\begin{bmatrix}a_x\newline a_y\end{bmatrix}=\begin{bmatrix}\cos\theta a_x-\sin\theta a_y\\sin\theta a_x+\cos\theta a_y\end{bmatrix}$
线段
定义方法：struct Segment {Point a,b;};
- 判断点 $P$ 是否在线段 $AB$ 上：
- 点 $P$ 在 $AB$ 所在直线上:$\vec{PA}\times\vec{PB}=\vec{0}$。
- 点 $P$ 在 $AB$ 之间：$\vec{PA}\cdot \vec{PB} \le 0 $ 或 $\begin{cases}\min{A_x,B_x}\leq P_x\leq\max{A_x,B_x}\\min{A_y,B_y}\leq P_y\leq\max{A_y,B_y}\end{cases}$
- 判断线段 $AB$ 和 $CD$ 是否相交（两种可能）：
- 点 $A$ 和点 $B$ 在直线 $CD$ 的不同侧，且点 $C$ 和点 $D$ 在直线 $AB$ 的不同侧（使用 to-left 测试）
- 三点共线或四点共线（验证是否有某线段的端点在另一线段上的情况）
例题：Magic Rabbit
直线
定义方法： struct Line {Point p,v;};（点向式，特别地，控制 $\vec{OP}+\lambda \vec{v}$ 中 $\lambda$ 的取值范围，该式子也可以用于表示线段或射线）。
多边形
定义方法：struct Polygon {vector<Point> p;};
- 一般情况下，按逆时针顺序排列点。
- 多边形面积 $S=\frac12\left|\sum_{i=0}^{n-1}\overrightarrow{OP_i}\times\overrightarrow{OP_{(i+1)\operatorname{mod}n}}\right|$，点 $O$ 在多边形内外均可。
- 判断点是否在多边形内：
- 光线投射算法：从该点引出一条射线（通常取水平线或竖直线），如果这条射线与多边形有奇数个交点，则该点在多边形内部，否则该点在多边形外部（交点为多边形顶点时，将该顶点视作在射线上侧，即所有边界的上端点和下端点只有一个是视作有效的）。
- 需要特判点在多边形上的情况
- 回转数法：面内闭合曲线逆时针转圈，闭合曲线绕过该点的总次数称为回转数。当回转数为 $0$，点在曲线外部。
- 一种实现方式是计算相邻两边夹角的和，注意夹角是有方向的。
- 凸多边形：$n$ 次 to-left 测试。
圆
定义方法：struct Circle {Point c; double r;};
基础计算几何模型
极角序
极角序，即将若干个向量根据极角进行排序，通常认为的顺序是从 $-\pi$ 开始逆时针旋转至 $\pi$。
极角序排序可以通过 atan2(y,x) 或 atan2l(y,x) 计算后进行排序，但精度较低，更优秀的方法是根据 下半平面<原点<$x$ 正半轴<上半平面<$x$ 负半轴 的方式划分为若干个区间后，对于同一区间内的向量根据叉积的正负性（即 to-left 测试）进行排序。
凸包/凸多边形
大部分摘抄自俊杰的 PPT。
构建凸包：Andrew’s algorithm
- 对点集以x坐标为第一关键字，y坐标为第二关键字排序
正序遍历每个点，用栈维护下凸包
倒序遍历每个点，用栈维护上凸包
时间复杂度为 $O(n\log n)$。
通过该算法，不仅可以找到凸包，还可以方便地维护出上下凸包，而上下凸包在凸包上二分等一系列算法中是进场能够用到的。
旋转卡壳
旋转卡壳用于求出点集的直径（其一定是凸包上的某两个极点的连线长度）。
- 设定初始边指针 $p$，并找到其对踵点指针 $q$（$O(n)$ 暴力找）。
$p$ 指向下一条边.
如果 $q$ 点到 $p$ 边的距离小于等于 $q$ 的下一个点到 $p$ 边的距离，则 $q$ 指向下一个点.
重复 3 直到找到 $p$ 边的对踵点，更新答案.
回到 2.
时间复杂度为 $O(n)$。
凸多边形上二分
大部分摘抄自俊杰的 PPT。
凸多边形上二分是一种思想，一系列问题都可以通过凸多边形上二分来解决。
判断点是否在凸多边形中
法一：分别在上下凸壳利用 $x$ 坐标序二分
- 最左和最右的点将凸多边形分成上下凸壳
- 通过一次to-left测试找出点在上半部分还是下半部分
- 通过二分查找找出点在哪两条竖线之间
- 最后与对应边进行一次to-left测试，确定其是否位于凸多边形内
时间复杂度：$O(\log n)$
法二：利用极角序二分
- 从最下的点出发向其他各点连射线，这些射线方向是按极角序排好的
- 通过to-left测试与二分查找，可以找出点在哪两条射线之间
- 再与对应边进行to-left测试，确定其是否位于凸多边形内
时间复杂度：$O(\log n)$
判断直线是否与凸多边形相交
- 凸多边形各边对应的向量是按照极角排好序的
- 二分查找直线的方向向量（正反两个方向），其前驱边与后继边的共同顶点处即为切点
- 也可以分为上下凸壳进行二分
时间复杂度：$O(\log n)$
过一点求凸多边形切线
对于凸包上一点 $V_i$，如果 $V_{i+1}$ 在射线 $PV_i$ 左侧，则 $V_i$ 点标记为 L，否则标记为 R.
如果 $V_{i-1}$ 的标记与 $V_i$ 不同，则 $V_i$ 是切点.
法一：上下凸壳
- 情况一：点在左极点左侧或右极点右侧
- 此时切点一个在上凸壳一个在下凸壳
- 上下凸壳的序列都满足 “LL…LLRR…RR” 或 “RR…RRLL…LL”，各自二分即可
- 情况二：两个切点均在上凸壳或下凸壳
- 以上凸壳为例，此时的序列为 LL…LLRR…RRLL…LL
- 二分找到 $x$ 坐标离该点最近的点，然后将上凸壳分为两部分，这两部分上又可以各自二分找到切点
时间复杂度：$O(\log n)$
法二：射线划分·改
- 情况一：序列中第一个点是 R，则序列形如 “RR…RRLL…LLRR…RR”
- 如果把最开始的几个 R 视作 L，那么序列则转化为可以二分的形式，并且可以二分找到切点
- 最开始的几个 R 一定在第一条切线的右侧
- 情况二：序列中第一个点是 L，则序列形如 “LL…LLRR…RRLL…LL”
- 如果把最后的几个 L 视作 R，那么序列则转化为可以二分的形式，并且可以二分找到切点
- 最后的几个 L 一定在第一条切线的右侧
时间复杂度：$O(\log n)$
这部分的板子先咕咕咕，可以参考文章开头俊杰哥哥的板子。
代码
极角序排序
struct Point{
int x,y;
}a[N];
int CheckDivision(Point i){
if(i.y<-eps) return 1;
if(i.y>eps) return 4;
if(i.x>eps) return 3;
if(i.x<-eps) return 5;
return 2;
}
ll cross(Point i,Point j){
return (ll)i.x*j.y-(ll)i.y*j.x;
}
bool argcmp(Point i,Point j){
int divx=CheckDivision(i),divy=CheckDivision(j);
if(divx!=divy) return divx<divy;
return cross(i,j)>eps;
}
构建凸包与旋转卡壳
struct Point{
ll x,y;
bool operator < (const Point& a)const{
if(x!=a.x) return x<a.x;
return y<a.y;
}
Point operator - (const Point& a)const{
return {x-a.x,y-a.y};
}
double length() const{
return sqrt(x*x+y*y);
}
ll len2() const{
return x*x+y*y;
}
ll toleft(const Point& a) const{
return x*a.y - y*a.x;
}
}a[N];
vector<Point> vec,con;
int n;
void Construct_Convex(){
//st 中存的就是凸包，注意，第一个点会出现两次，即最开始和最后
sort(vec.begin(),vec.end());
con.push_back(vec[0]);
for(int i=1;i<vec.size();i++){
while(con.size()>1){
Point t1=con[con.size()-2],t2=con[con.size()-1];
if((t2-t1).toleft(vec[i]-t2)<=0) con.pop_back();
else break;
}
con.push_back(vec[i]);
}
reverse(vec.begin(),vec.end());int k=con.size();
for(int i=1;i<vec.size();i++){
while(con.size()>k){
Point t1=con[con.size()-2],t2=con[con.size()-1];
if((t2-t1).toleft(vec[i]-t2)<=0) con.pop_back();
else break;
}
con.push_back(vec[i]);
}
}
ll area(Point p1,Point p2,Point p3){
return abs((p2-p1).toleft(p3-p1));
}
ll Rot_Caliper(){//返回凸包的直径
if(con.size()==2) return 0;//注意，第一个点会出现两次
if(con.size()==3) return (con[0]-con[1]).len2();
int i=0,j=1;
ll ans=0;
for(int k=0;k<con.size();k++){
if(area(con[i],con[i+1],con[k])>=area(con[i],con[i+1],con[j])){
j=k;
}
}
while(i<con.size()-1){
int tmp=j+1;if(tmp==con.size()-1) tmp=0;
while(area(con[i],con[i+1],con[tmp])>=area(con[i],con[i+1],con[j])){
j=tmp;tmp=j+1;if(tmp==con.size()-1) tmp=0;
ans=max(ans,(con[j]-con[i]).len2());
ans=max(ans,(con[j]-con[i+1]).len2());
}
i++;
}
return ans;
}