圆基础

• 圆的表示：圆心、半径 $r\ge 0$。除非特别说明，下文的圆与圆关系、交点和公切线公式均假设半径严格为正；$r=0$ 时图形退化为一个点，需要单独处理
• 圆的周长：$C=2\pi r$
• 圆的面积：$S=\pi r^2$

圆的关系问题

点与圆的关系

• 点在圆外
• 点在圆上
• 点在圆内

判定方法：将点到圆心距离的平方与半径平方比较，可以避免开平方。

平方比较只避免了开平方，并不会自动消除误差。输入及中间运算采用精确数值表示且不溢出时，比较结果才是精确的；算法竞赛中最常见的情形是整数输入，并使用足够宽的中间类型。例如输入为 long long 时，中间乘积常需使用 __int128。若输入为浮点数，平方比较仍有舍入误差，需要使用与数据尺度匹配的容限。

直线与圆的关系

• 相离
• 相切
• 相交

设直线为 $\overrightarrow{X}=\overrightarrow{P}+t\overrightarrow{v}$，其中 $\overrightarrow{v}\ne \overrightarrow{0}$，圆心为 $C$。可以比较

$$[\overrightarrow{v}\times (\overrightarrow{C}-\overrightarrow{P}){]}^2\text{与}{r}^2(\overrightarrow{v}\cdot \overrightarrow{v})$$

来区分相离、相切和相交，从而避免除法与开平方。该比较在数值及中间运算均精确且不溢出时可以得到精确结果；浮点输入仍需容限。

圆与圆的关系

令两个正半径圆的半径分别为 $r_1,r_2$，圆心距离为 $d$。按下列顺序判断可以得到互斥分类：

• 相同：$d=0$ 且 $r_1=r_2$；
• 同心但不同圆：$d=0$ 且 $r_1\ne r_2$，较小圆严格内含于较大圆；
• 相离：$d>r_1+r_2$；
• 外切：$d=r_1+r_2$；
• 相交于两点：$|r_1-r_2|<d<r_1+r_2$；
• 内切：$d=|r_1-r_2|$；
• 严格内含：$0<d<|r_1-r_2|$。

若讨论圆盘的覆盖关系，则较小圆盘被较大圆盘完全覆盖当且仅当

$$d+min(r_1,r_2)\le max(r_1,r_2).$$

浮点实现中的相等关系均应使用容限。若允许零半径，应先把退化圆当作点处理，否则同圆、内切和外切条件可能同时成立，以上分类及后续切线数量表不再适用。

交集问题

直线与圆的交点

前提：直线方向向量 $\overrightarrow{v}\ne \overrightarrow{0}$，且直线与圆不相离。

​直线：$\{P,\overrightarrow{v}\}$

​圆：$\{C,r\}$

设圆心到直线的距离为 $d$，投影点为 $C^{\prime }$，则交点为

$$C^{\prime }\pm {\displaystyle \frac{\sqrt{max(0,r^2-d^2)}}{|\overrightarrow{v}|}}\overrightarrow{v}.$$

相切时根号部分为 $0$，两个表达式表示同一个点。max 用于吸收浮点误差造成的微小负数；它不能代替前面的相交关系判断。

圆与圆交点

以下公式要求 $r_1,r_2>0$、$d>0$，且

$$|r_1-r_2|\le d\le r_1+r_2.$$

重合圆有无穷多个交点；相离、严格内含或同心但半径不同的圆没有交点，这些情况均应在使用公式前返回。

​两圆圆心连线与一圆心到交点连线夹角 $\alpha$。

根据余弦定理，先计算

$$c={\displaystyle \frac{r_1^2+d^2-r_2^2}{2r_{1}d}},$$

浮点实现中将 $c$ 限制到 $[-1,1]$，再令

$$\cos \alpha =c,\sin \alpha =\sqrt{max(0,1-c^2)}.$$

严格相交时可得到两个交点；内切或外切时 $\sin \alpha =0$，两个结果重合，只应返回一个交点。

​将两圆心连线对应向量进行伸缩旋转。

圆与多边形面积交

按多边形的每条有向边 $P_i{P}_{i+1}$，计算有向三角形 $C{P}_i{P}_{i+1}$ 与圆盘的带符号面积贡献，全部求和后再取绝对值。对凹多边形不能把各三角形贡献分别取绝对值后直接相加，否则重叠或位于外部的部分无法正确抵消。

多个圆的面积并

这里求的是多个圆盘覆盖区域的面积。预处理时应先丢弃零半径圆，将完全相同的圆去重；若圆 $i$ 满足

$$d_{ij}+r_i\le r_j,$$

则圆盘 $i$ 被圆盘 $j$ 完全覆盖，不会贡献圆并边界。相等比较在浮点实现中需要容限，但不能把带 eps 的比较器直接用于排序。

对保留下来的每个圆，求出其边界被其它圆覆盖的极角区间。只有严格部分相交的两圆才需要生成覆盖角区间；若通过 acos 计算半角，应先将浮点余弦值限制到 $[-1,1]$。跨越 $2\pi$ 的区间应拆成两段；无覆盖区间时，整个圆周均为可见边界。扫描角度事件时，同一极角的所有事件必须分组后统一更新覆盖计数，不能依赖同角事件的任意先后顺序。实际排序应使用严格比较，再在排序结果中按容限合并近似同角事件。

设当前圆心为 $(x_0,y_0)$、半径为 $r$。对按逆时针方向遍历、极角从 ${\theta }_l$ 到 ${\theta }_r$ 的一段可见圆弧，它对边界积分 $\oint (xdy-ydx)$ 的贡献为

$$2S_{\mathrm{arc}}=x_{0}r(\sin {\theta }_r-\sin {\theta }_l)-y_{0}r(\cos {\theta }_r-\cos {\theta }_l)+r^2({\theta }_r-{\theta }_l).$$

将所有可见圆弧的贡献相加再除以 $2$，即可得到圆并面积。每个圆产生并排序 $O(n)$ 个事件时，总时间复杂度为 $O(n^2\log n)$。

切线问题

过圆外一点圆的切线

设点到圆心的距离为 $d$，本节要求 $r>0$ 且 $d>r$。令

$$c={\displaystyle \frac{r}{d}},$$

浮点实现中先将 $c$ 限制到 $[-1,1]$，再使用 $\cos \alpha =c$。

• 向量伸缩、旋转

点在圆上时只有一条切线，点在圆内时没有实切线，应在套用上述构造前分别处理。

两圆的公切线

以下数量按不同的几何直线计数，并要求两个圆的半径均为正：

• 相同：无穷多条；
• 相离：$4$ 条；
• 外切：$3$ 条；
• 相交：$2$ 条；
• 内切：$1$ 条；
• 内含或同心但不同圆：$0$ 条。

外切时两条重合的内公切线只计作一条，内切时两条重合的外公切线也只计作一条。零半径圆退化为点，不适用这张切线数量表。

外公切线

对两个不同且非同心的正半径圆，外公切线构造使用

$$c={\displaystyle \frac{r_1-r_2}{d}}.$$

仅当 $|r_1-r_2|\le d$ 时存在外公切线。浮点实现应将 $c$ 限制到 $[-1,1]$ 后再计算角度。

内公切线

内公切线构造使用

$$c={\displaystyle \frac{r_1+r_2}{d}}.$$

仅当 $r_1+r_2\le d$ 时存在内公切线。同样应先将浮点计算得到的 $c$ 限制到 $[-1,1]$。

圆的反演

​给定反演中心点 $O$ 和反演半径 $R$，若平面上点 $P$ 和 $P^{\prime }$ 满足：

• 点 $P^{\prime }$ 在射线 $OP$ 上
• $|\overrightarrow{OP}|\times |\overrightarrow{O{P}^{\prime }}|=R^2$

​则称点 $P$ 和点 $P^{\prime }$ 互为反演点。

​性质：

• 圆外的点的反演点在圆内，反之亦然
• 圆上的点的反演点为其自身
• 不过点 $O$ 的圆，其反演图形也是不过点 $O$ 的圆
• 过点 $O$ 的圆，其反演图形是不过点 $O$ 的直线
• 两个图形相切，则它们的反演图形也相切

最小圆覆盖

问题描述：给定平面上 $n$ 个点，求一个半径最小的圆，能覆盖所有的点。本节约定空点集返回空值，因为最小半径虽可取 $0$，但圆心不唯一；若具体接口选择返回以原点为圆心的零圆，也必须明确这是人为约定。

边界情况：

• 一个点的最小覆盖圆以该点为圆心，半径为 $0$；所有点重合时同理；
• 两个不同点的最小覆盖圆以它们的中点为圆心，以两点距离的一半为半径；
• 三个不共线的点可以唯一确定外接圆；
• 三个点共线时不能直接套用外心公式，覆盖它们的最小圆由最远点对作为直径确定。

​定理：如果点 $p$ 不在点集 $S$ 的最小圆覆盖圆内，那么它一定在 $\{p\}\cup S$ 的最小覆盖圆上，即最小覆盖圆一定经过点 $p$。

将输入点按与原顺序独立的均匀随机排列打乱后，使用随机增量算法可以得到期望 $O(n)$ 的时间复杂度。常见三重循环实现的最坏时间复杂度仍为 $O(n^3)$；随机化影响的是期望运行时间，不影响算法返回结果的正确性。