Offer 收割编程练习赛 87B 方圆距离

与坐标轴平行的矩形和圆的位置关系。

分两种情况。

圆与矩形交集不为空

此时答案为零。问题归结为如何判断圆与矩形交集不为空。

先排除矩形顶点在圆内或圆心在矩形内。
此时，若矩形与圆交集不为空，则必有矩形的某条边穿过圆（「穿过圆」也可表述为「割圆」，「线段穿过圆」的确切定义为「线段与圆周有两个交点」）。注意：这样的边可能不止一条。

问题归结为如何判断线段是否割圆。

线段割圆的充要条件是圆心到线段所在直线的垂直投影落在线段上，且圆心到投影的距离小于半径。

矩形的左下顶点为 $(x_1, y_1)$，右上顶点为 $(x_2, y_2)$，圆心为 $(x, y)$，半径为 $r$ 。
不失一般性，考虑矩形的底边 $(x_1, y_1) , (x_2, y_1)$ 割圆的条件。

性质

在排除了矩形的某个顶点在圆内或圆心在矩形内的条件下，矩形的底边上有点在圆内当且仅当
$x_1 < x < x_2$ 且 $|y - y_1| \le r$ 。

其余边的情形是类似的。

圆与矩形交集为空的情形

此时应当注意到：

矩形上距离圆周最近的点必然在边界上。
矩形边界上任意一点 $P$ 到圆周的最短距离为 $|PC| - r$，$|PC|$ 表示 $P$ 到圆心 $C$ 的距离。
问题归结为求圆心 $C$ 到矩形边界的最短距离，亦即点到线段的最短距离。

备选的点（candidates）是圆心在四条边所在的直线上的垂直投影（即垂足）与边的端点。
如果「圆心在矩形的某条边所在的直线上的垂直投影」落在这条边上则此投影点是这条边上的备选点，否则这条边的两端点是这条边上的备选点。

（这一部分内容还在建设中）

举一反三

如果矩形不是坐标轴平行的，通过坐标变换就可以转化到坐标轴平行的情形。
如何进行坐标变换？

首先假设我们想要的坐标变换是一个线性变换。

任取矩形的一个顶点 $A$，作为此线性变换的不动点。设 $A$ 的坐标为 $(x_A, y_A)$ 。
任取 $A$ 的一个邻点 $B$，使得 $\vec{AB}$ 是变换过后的 $x$ 轴正方向，亦即 $B$ 变换过后的坐标为 $(x_A + |AB|, y_A)$，$|AB|$ 表示线段 $AB$ 的长度。

将矩形换成任意凸多边形怎么做？

问题归结为求点到线段的最短距离。

巴特西

Offer 收割编程练习赛 87B 方圆距离

圆与矩形交集不为空

圆与矩形交集为空的情形

举一反三

最新文章

热门文章