计算几何 学习笔记
推荐阅读这个，模板可在这里找strangeman的提交记录。
向量相关
向量的坐标表示
有点 $A(x_1,y_1)$ 和点 $B(x_2,y_2)$，则 $\overrightarrow{AB}$ 可表示为 $(x_2-x_1,y_2-y_1)$
共线向量
共线向量 $a(x_1,y_1)$ 和 $b(x_2,y_2)$ 满足
$$
x_1y_2=x_2y_1
$$
由此得到判断三点共线的方法：计算 $\overrightarrow{AB}$ 和 $\overrightarrow{BC}$ 进行比较。
向量的点乘
向量 $a(x_1,y_1)$ 和 $b(x_2,y_2)$ 的数量积
$$
a \cdot b=x_1x_2+y_1y_2
$$
由此得到向量垂直的条件：
$$
a\perp b \Leftrightarrow x_1x_2+y_1y_2=0
$$
向量的叉乘
向量 $a(x_1,y_1)$ 和 $b(x_2,y_2)$ 的向量积
$$
a \times b=x_1y_2-y_1x_2
$$
叉乘的意义
若两个向量的叉积不为 $0$，则他们相交；否则他们重合或平行。
两个向量的叉积是他们围成的平行四边形的面积，由此可以快速计算三角形的面积，从而快速计算多边形的面积。注意：逆时针求得的面积是正的，顺时针求得的是负的。
若两个向量的叉积大于 $0$,则第二个向量由第一个逆时针选择得到；反之由顺时针旋转得到。由此可以判定多边形的凹凸性、判定点与多边形的位置关系、判定线段相交等等。
多边形相关
三角函数
$\pi=\arccos(-1)$，这样精度比较高。
开平方、反三角函数最容易炸精度。因此不要使用正弦定理求解角度，尽量使用余弦定理或点乘。还有个好处就是余弦值在 $[0,\pi]$ 是唯一的！
凸包与面积
求凸多边形的面积的基本思想是三角剖分后求每个三角形的面积。由此产生了两种子类型：
1.在动态凸包中处理。则每次增加点、删除点的面积与该点和相邻两点组成的三角形的面积相关；
2.以某一点为基准点处理。则面积与基准点和当前边构成的三角形的面积相关，注意三点共线的情况要特判。