计算几何

向量

高一知识，略讲。

向量外积

若 \(\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(...) 表示其模长。