杂项

两条直线交点

设两条直线分别由 $(x_1,y_1)$ 和 $(x_2,y_2)$、以及 $(x_3,y_3)$ 和 $(x_4,y_4)$ 相连得到，则它们的交点表示为 $\left(\frac{x_p}{q},\frac{y_p}{q}\right)$，其中

auto px = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4);
auto py = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4);
auto q = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);

IMPORTANT

小心越界。

旋转矩阵

二维旋转矩阵：

$$\left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\end{array}\right]=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right].$$

切比雪夫距离

$$d(A,B):=\max (|x_1-x_2|,|y_1-y_2|).$$

• 将一个点的坐标变为 $(x+y,x-y)$ 之后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离；
• 将一个点的坐标变为 $\left(\frac{x+y}{2},\frac{x-y}{2}\right)$ 之后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。