计算几何
向量
高一知识，略讲。
向量外积
若 \(\vec x = (x_1, y_1), \vec y = (x_2, y_2)\)，则有 \(\vec x \times \vec y = x_1 y_2 - y_1 x_2\)。
或者表示为 \(|\vec x||\vec y| \sin \theta\)，其中 \(\theta\) 表示向量间的夹角。
几何意义：两个向量构成的平行四边形的面积（可以为负数）。
性质：
- 若 \(\vec x \times \vec y \gt 0\)，则 \(\vec y\) 在 \(\vec x\) 的逆时针方向，反之亦然。
向量旋转
将一个向量顺时针旋转 \(\alpha\)，可以利用矩阵的性质。
对于向量 \(\vec x = (x, y)^T\)，旋转公式为：
\[(x, y) \begin{pmatrix} \cos \alpha & -\sin \alpha \\ \sin \alpha & \cos \alpha \end{pmatrix} \]逆时针旋转的矩阵为其转置矩阵：
\[(x, y) \begin{pmatrix} \cos \alpha & \sin \alpha \\ -\sin \alpha & \cos \alpha \end{pmatrix} \]矩阵可以不好理解，可以通过极坐标推导。这里不展开。
向量的极角
定义为向量与 \(x\) 轴正半轴的夹角，一般用 \(atan2(y, x)\) 实现。
\(atan(y, x)\) 的取值范围为 \([-\pi, \pi]\)。
点
利用一个向量 \(\vec x\) 表示其坐标。
这个向量等价于原点到目标点的向量。
线
可以用多种方法表示，视情况而定：
-
一般式表达：\(Ax＋By + C = 0\)。方便表示一条直线，或者无向的线段。
-
两个点表达：\((x_1, y_1) \to (x_2, y_2)\)，可以方便表示有向的线段或者射线。
-
点与向量：\((x,y) + k \vec d\)，可以方便的表示射线。
补充：
两个点求解一般式，有 \(A = y_2 - y_1, B = x_1 - x_2, C = x_2y_1 - x_1 y_2\)。
判断两个一般式直线平行，用：\(A_1B_2 = A_2B_1\)。本质是求斜率。
求一般式的交点，将式子变为：
\[A_1 A_2 x + B_1 A_2 y + C_1 A_2 = 0 \\ A_2 A_1 x + B_2 A_1 y + C_2 A_1 = 0 \\ \]相减可得：
\[y = (C_1 A_2 - C_2 A_1) / (A_1 B_2 - A_2 B_1) \]同理可得：
\[x = (C_2 B_1 - C_1 B_2) / (A_1 B_2 - A_2 B_1) \]需要保证两条直线不平行！
线线交点
首先排除平行与重合的情况，判断是否相交，利用向量外积即可。
判断有无交点：若 \(\vec {AC} \otimes \vec {AD}\) 和 \(\vec{AC} \otimes \vec {AB}\) 异号，以及 \(\vec {BD} \otimes \vec {BA}\) 和 \(\vec {BD} \otimes {BC}\) 异号，则有交点。
然后可以利用面积法求交点。
用向量外积求出 \(S_{ABCD}\)，以及 \(S_{ABD}\)。
那么 \(AO : AC = S_{ABD} : S_{ABCD}\)，然后就可以找出 \(O\) 的坐标了。
点在线上
线上去两点 \(S, T\)，对于点 \(P\)，若 \(P\) 在线段 \(ST\) 上，则 \(\vec{SP} \otimes \vec {PT} = 0\)。
反之不一定成立，需要再判断坐标范围。
点关于直线对称
先找到垂线长度，可以利用向量外积达成。
在直线上任取两个点，利用向量外积求出所构成的三角形的面积，进而求出垂线长度。
利用这两个点，找到在直线方向上的单位向量，旋转 \(\frac \pi 2\)，乘上垂线长的二倍，与原坐标相加即可。
Point flip(Point p, Point st, Point ed) {
double h = (st - p) * (ed - p) / abs(ed - st);
Point I = (ed - st) / abs(ed - st);
return p + ((Point){I.y, -I.x}) * 2 * h;
}
其中 abs(...) 表示其模长。
可能需要注意方向！
多边形
一般按照顺时针或者逆时针的方向一一列出所有的顶点。
判断顺时针或者逆时针
钦定一个起点，编号为 \(1\)。
枚举 \(i\) 利用 \(\vec{1i}\) 和 \(\vec{1(i+1)}\) 的叉乘，可以算出整个多边形的面积(的两倍)。
但是考虑到叉乘的正负性，如果结果为正，则所给的顺序为逆时针（因为 \(\vec{1i}\) 在 \(\vec{1(i+1)}\) 的顺时针方向）。
判断凸多边形
判断折线段拐向是否相同：
对于折线 \(A \to B \to C\)，若 \((B - A) \otimes (C - B) \lt 0\)，则为顺时针，反之为逆时针。
判断点在多边形内
有很多方法，这里说两种常用的。
-
通用射线法：从该点做一条射线，如果该射线与多边形的交点数为奇数，则在内部，反之在外部。
-
凸多边形二分法：略
闵可夫斯基和
略……QwQ
凸包算法
Graham 算法
首先极角排序，然后单调栈做一遍，好写不易错！
不过需要注意的是，在极角相同的情况下，要按照距离 原点 排序。
标签：26,Point,笔记,外积,算法,vec,otimes,alpha,向量 From： https://www.cnblogs.com/jeefy/p/17572843.html