计算几何：圆

圆的数据结构定义

1
2
3
4

struct circle {
    point c; // 圆的中心
    real r; // 半径
};

注意事项

• 尽量避免直接用 (long) double 进行操作，考虑到浮点误差，更建议使用向量操作

圆与直线

过某点做某圆的切线

过一个点 $P$ 做圆 $C$ 的切线

若点 $P$ 在圆上，则切线垂直于半径 $CP$，直接令直线 $\texttt{s=\(P\), d=perp(\(\vec{CP}\))}$.

否则 $P$ 在圆外，否则没有切线。此时有两条切线，且应当关于 $CP$ 对称。考虑用误差更小的向量组合求出 $D$，然后另一边也能求了。

弦切角定理

令 $|CP|=d$，推理 $\Delta PCD$ 的面积，发现 $|AD| = \frac{r\sqrt{d^2-r^2}}{d}, |AP|=\frac{d^2-r^2}{d}$

所以 $D = P+|AP|\cdot \vec{PC} \plusmn |AD|\cdot \texttt{perp}(\vec{PC})$

1
2
3
4
5
6
7
8
9
10
11
12

std::vector<line> tangent(point x, circle c) {
    real d = distance(c.c, x);
    std::vector<line> res = {};
    if (d == c.r) res.push_back(line{x, perp(c.c - x)}); // 点在圆上
    else if(d > c.r) { // 点在圆外
        real c1 = (d.sqr() - c.r.sqr()) / d;
        real c2 = c.r * (sqrt(d.sqr() - c.r.sqr())) / d;
        res.push_back(line{x, (c.c-x).rescale(c1) + (c.c-x).Rrot().rescale(c2)});
        res.push_back(line{x, (c.c-x).rescale(c1) + (c.c-x).Lrot().rescale(c2)});
    } // 否则点在圆内
    return res;
}

圆与三角形

三角形外接圆、三点定圆

给定不共线的三个点 $A,B,C$，求圆 $P$ 过三个点。

由于是三点共圆，所以 $|AP| = |BP| = |CP|$，于是，我们可以求出 $AB$ 与 $BC$ 的中垂线，则这两条中垂线的交点必然就是圆心。于是半径也很容易求了。

三角形内切圆

给定三角形 $\Delta ABC$，求出其内切圆。

圆与圆

两圆的公切线

我们首先需要就两圆的不同位置情况进行分类讨论，以下，我们假设圆 $A$ 的半径 $r_1$ 大于圆 $C$ 的半径 $r_2$，且令 $|AC| = d$

两圆内含

显然，这个情况下没有公切线。

两圆内切

此时，只有一条公切线，如下图所示

我们找出直线 $AC$ 的表达式，并且找出 $B$ 的坐标，然后过 $B$ 作 $AC$ 垂线。

怎么找出 $B$ 点坐标呢？考虑到 $A,B,C$ 三点共线，于是有 $B=A+\vec{AC}\cdot \frac{r_1}{d}$

两圆相交

作圆

同时与两条直线相切，作给定半径的圆

同时与直线 $u,v$ 相切，半径为 $r$ 的圆

我们先把两条直线沿垂线平移 $\plusmn r$ 的距离，这样就有 $2\times 2$ 个交点可以作为圆心。

得到与给定直线相切、过某点、半径给定的圆

得到与直线 $u$ 相切，过点 $Q$，半径为 $r$ 的圆

同理，先将直线 $u$ 平移 $\plusmn r$ 的距离得到 $u_1,u_2$，然后任务就变成了，在两条新的直线上，找点 $P$，使得 $|PQ|=r$

所以，先求出 $Q$ 到 $u_i$ 的距离和垂足 $H$，用勾股定理计算 $P$ 到垂足 $H$ 的距离，然后向量加即可。

过两点，半径给定的两个圆

得到过 $a, b$ 两点，半径为 $r$ 的两个圆

先作出 $a,b$ 中垂线，然后在中垂线上取点即可。

圆上定理

托勒密定理

圆幂定理