计算几何入门

1 注意事项

• 在计算几何中，没有 float 只有 double 和 long double 。其中 double 的格式化输入为 lf ，long double 为 LF 。
• 在计算几何中，判断实数相等不能直接写 x==y ，会有精度误差，应该写一个判断，看是否 fabs(x-y)<=eps 其中 \(eps\) 是一个很小的实数，有 \(10^{-8}\) 左右。

2 前置知识

2.1 向量

向量有方向和长度，任何一个向量与坐标系上的坐标一一对应，向量的线性运算就是坐标的线性运算。

在二维向量中的数量积（点积）和向量积（叉积）

同时因为数量积与投影有关，所以可以根据数量积来算投影的长度。

要证明数量积和向量积与坐标之间的关系，直接把向量分解到坐标轴上，然后用交换律、结合律、分配律，再利用垂直时的运算特点就可以得到证明。

这里挂上三维向量的博客

注意叉乘的正负号有特殊的含义，即如果为正号，那么说明从第一个向量到第二个向量为逆时针，否则为顺时针。

在二维中，叉乘是一个数值，这个和三维不同。

2.2 直线

• 解析法：\(y=kx+b\)
• 双点法：用两个点表示一条直线。
• 点向法：用一个点和一个向量表示一条直线。这种方法是 zhx 推荐的。

2.2.1 求垂直直线

当前直线的向量为 \((x,y)\) ，那么垂直之后的向量为 \((y,-x)\)

除非解方程，否则不要用解析式。

2.2.2 点到直线距离

给定点 \(P,Q\) 和向量 \(a\) ，其中 \(P,a\) 表示一条直线，然后求解 \(Q\) 到这条直线的距离。

我们从 \(P\) 向 \(Q\) 引一条向量 \(b\)，那么这个距离实际上是 \(|b|\sin\alpha\) 其中 \(\alpha\) 为向量 \(a,b\) 夹角，不难发现，这个值实际上就是 \(\frac{a\times b}{|a|}\)

2.2.3 求两条直线交点

解析式就是解方程，但是如果有常数方程需要特判，比较麻烦。

我们用两点法来做这个。

首先两点法可以与点向法互相转化，只需要把所有的点看做从原点向该点的一条向量，那么转化就可以看成是向量之间的运算，直接在坐标上加减就可以。

设 \(A,B\) 为一条直线上两点，\(C,D\) 为另一条直线上两点，设 \(E\) 为交点。

显然我们有：

\[\overrightarrow{OA}+\overrightarrow{AE}=\overrightarrow{OE}\\ \overrightarrow{AE}=\overrightarrow{AB}\times \frac{|\overrightarrow{AE}|}{|\overrightarrow{AB}|} \]

这个比值怎么办， 我们来一张图以便于说明。

其中两条直线是 \(AB\) 和 \(CD\) ，\(E\) 是他们的交点。

我们有：

\[\frac{\overrightarrow{AE}}{\overrightarrow{AB}}=\frac{AF}{AF-BG}=\frac{S_{\Delta ACD}}{S_{\Delta ACD}-S_{\Delta BCD}}=\frac{S_{\Delta ACD}}{S_{\Delta ABC}+S_{\Delta ABD}}\\ =\frac{\overrightarrow{CA}\times \overrightarrow{CD}}{\overrightarrow{AB}\times \overrightarrow{AC}+\overrightarrow{AD}\times \overrightarrow{AB}}=\frac{\overrightarrow{CA}\times \overrightarrow{CD}}{\overrightarrow{AB}\times \overrightarrow{AC}-\overrightarrow{AB}\times \overrightarrow{AD}}=\frac{\overrightarrow{CA}\times \overrightarrow{CD}}{\overrightarrow{AB}\times \overrightarrow{DC}} \]

所以这个就可以做了。

注意，需要特判分母是否为 \(0\) ，如果为 \(0\)，那么两条直线重合。这种情况下我们认为没有交点。

2.3 多边形

多边形凸凹：若存在一个内角大于 \(180\) 度则为凹，反之为凸。

2.3.1 判断一个点是否在多边形内部

射线法。从多边形内部这个点开始随机的引一条射线，如果在多边形内部，那么交点一定是奇数个，外部则一定是偶数个。

不过这种方法可能会出错，比如这张图：

第一种处理方法是一直随机随机到与端点不交，这样就没有问题了。

第二种处理方法是看那个交点相邻的两条边，如果需要算两次，那么必定是在异侧，如果需要算一次，那么必定是在同侧，比如这张图：

至于判断是否在同侧就用这条射线与与端点相邻的两条边做向量积然后判断乘积的正负就可以了。正则为同侧，这种情况端点算两次，负则为一次，这种情况端点算一次。

所以我们可以特判这种情况。

那么如果直接与一条边重合怎么办？

我们还是判断除了与重合边重合的相邻两边是否在同侧就可以了。

说了这么多，其实还不如多随机几次，因为随机到端点的概率非常小，所以我们就可以认为不会随机到端点。

2.3.2 计算多边形面积

我们随机一个点，这个点在内外部无所谓，然后分成若干个三角形，然后按照一个顺序进行向量积，最后不要忘了除以二。向量积会自己帮我们处理“整体减空白”的操作，我们只需要保证点的顺序即可，即我们需要给每个点按某一顺序（顺时针，逆时针）标号。比如这张图：

不过可能最后符号会有问题，向量积只保证相互抵消，但不保证符号。我们需要加一个绝对值。

2.4 凸包

给定点集 \(S\) ，求最小的把所有点包住的凸多边形。

2.4.1 Grahan 水平线扫描法

我们用栈来维护这个凸包。

给定 \(n\) 个点，按照 \(x\) 从小到大（第一关键字）\(y\) 从小到大（第二关键字）排序。

最开始我认为凸包上有两个点，设凸多边形上的边是顺时针转，则角是逆时针转，这是我们判断一个角是凸角还是凹角的判断依据。

我们按照顺序把点依次加入，当出现凹角时，我们不断弹出栈顶，直到这个角是凸角，如果这个角是凸角，那么我们直接把这个点加入栈中。一直到第 \(n\) 个点。

但算法结束时，我们只能维护一个上凸壳。我们再从第 \(n\) 个点重新做这个算法，一直做到第 \(1\) 个点。这样我们就维护了一个下凸壳。两次弄得加起来就是一个凸包。复杂度 \(O(n\log n)\) ，瓶颈是排序。

2.4.2 动态凸包

假如我们有 \(3\) 个点，我们怎么求凸包？答：三个点不需要求凸包。这三个点组成了一个三角形。

我要算 \(n\) 个点的凸包，那么我们就需要一个点一个点的加入，我们不用管那些在内部的点，因为那些点没有贡献。我们接下来只考虑不在凸包内部的点。注意到随着点的加入，这个凸包一定会越变越大，我们考虑如何维护凸包。

我们从凸包内部维护一个点 \(O\) ，然后有一条水平水平线 \(OX\)。那么我们从凸包上所有点向 \(O\) 连边，形成多个与 \(OX\) 角，当我们需要加入点 \(P\) 时，我们找到两个点使得这两个点对应的角正好是 \(P\) 对应的角的前驱后继，然后我们从这个位置向两边删除形成凹角的点，直到是一个凸角，然后再加入点 \(P\) 。我们可以用平衡树来维护角度。因为每一个点最多被插入一次，删除一次，所以复杂度是 \(n\log n\) 。但实际上我们可以用一个 \(set\) 就可以解决问题。

这个做法虽然难写，但可以动态维护凸包。

2.4.3 最小矩形，旋转卡壳

给定 \(n\) 个点，找到一个最小的矩形，使得 \(n\) 个点都能被框住。

不难发现我们是用一个矩形去框一个凸包，并且最优框法是凸包的其中一条边与矩形重合，然后其对点也在矩形上。

我们可以枚举一个点，然后去看它对面那一条边，至于对面那条边的确定，我们可以算一下该点到每一条边的距离，距离最大的那个边就是对边，最大的那个距离就可以作为矩阵的高度。

观察到点在顺时针转时，对边也在顺时针转，我们从上一次的结果开始顺时针旋转，直到找到一个边，满足其邻边到点的距离都小于该边，这样我们就可以找到下一个对边。

我们可以让这个矩形的四条边一起转，这样就可以找到我们的最小矩形。

2.4.4 半平面交

每一条有方向的直线会把一个平面分成两块，我们始终保留半平面的左边，我们想要求解这些半平面的交。

我们考虑按照斜率对这些直线进行排序。考虑到斜率可以用角度来表示，所以我们干脆就按照角度来排序。

如果有若干条斜率相同的直线，保留最左边那一条。这样剩下的直线斜率个不相同。

注意到半平面交发生变化的位置一定是那些交点，所以我们只需要维护那些交点。当插入一条直线时，明显我们需要算一下这条直线与其他直线的交点。

所以当我们加入一条新边时，我们检查一下之前的交点是在这条新边的左边还有右边。如果在右边，那么这个点就没有用了，我们直接舍弃掉。对应的，这个交点对应的那条直线也没有用了。一直这样做下去就可以维护我们的半平面交。

注意这个需要删除的点可能在开头也可能在末尾，最后因为排序的问题我们仍然需要在把末尾节点与开始的直线，开始节点与末尾直线进行比较。这样就可以了。

3 例题

3.1 例题1

一共有 \(3\) 种合金，每一种合金由三种金属组成，比例为 \(a_i:b_i:c_i\) 。一共有 \(m\) 次询问，每次给出一种合金，问新给定的某种合金能否用 \(n\) 种合金组合而成。

令这三个比例变成 \(\frac{a_i}{a_i+b_i+c_i}:\frac{b_i}{a_i+b_i+c_i}:\frac{c_i}{a_i+b_i+c_i}\)

这样三个比例加起来就是 \(1\)。

这样的话，我们不用管 \(c_i\) ，只需要管 \(a_i\) 和 \(b_i\) ，因为这三个东西之和为 \(1\)。如果第一种合金为 \((a_1,b_1)\) 第二种合金为 \((a_2,b_2)\) 那么其所能够组成的合金为 \((ka_1+(1-k)a_2,kb_1+(1-k)b_2)\) 。

如果把上面这些点画在平面直角坐标系上， 会发现 \((a_1,b_1),(a_2,b_2)\) 能组成的合金对应的点是这两点之间的线段，如果是三个点，那么就是这个三角形。如果是多个点，那么就是这些点组成的凸包。

3.2 例题 2

给定 \(F(x)=\sum\limits_{i=1}^n\mu_ix_i,0\le \mu_i\le 1\) 且和为 \(1\) 。已知 \(F(x)=c\) ，给定 \(x,y,c\) ，要求 \(F(y)\) 的最大值和最小值。

\[F(x)=\mu_1x_1+\mu_2x_2...\mu_nx_n=c\\ F(y)=\mu_1y_1+\mu_2y_2+...\mu_ny_n \]

我们把所有 \((x_i,y_i)\) 弄在平面直角坐标系上，弄成一个凸包，实际上我们可以组成这个凸包上所有的点，而那个 \(c\) 其实是把答案限制到了 \(x=c\) 的直线上，我们只需要关注这条直线与凸包的交点的最上端。