更新题目 Draw Circle：不用浮点画圆
题目 everpure-draw-circle · 修改（rev 10） · · 2026-10-27 00:33
body
@@ -1,12 +1,12 @@ ## TL;DR -- **题**（题目一节）：圆心在原点、半径是整数 r，用现成的 `plot(x, y)` 点亮圆周经过的像素。题面很短，考的是后面一连串优化，开写前先问清题目一节表里那几点。 -- **只画恰好在圆上的整点不行**（思路第 1 节）：r = 3 时只有 (0, ±3)、(±3, 0) 四个点，follow-up「r 很小时多画几个点」要解决的就是这个。 -- **每一列取离圆最近的整数 y，还是会断**（第 2 节）：靠近 (±r, 0) 的地方圆很陡，x 加 1 时 y 一下掉好几格，每列只画一个点，中间就空了。 -- **只算 0° 到 45° 那八分之一，再 8 路对称**（第 3 节）：这一段里相邻两列真实高度差小于 1，所以 y 只会不变或减 1，画出来不断。循环条件直接写 `x <= y`。 -- **不开方**（第 4 节）：拿两个候选像素的中点代入 x² + y² − r²，小于 0 选上面的 y，大于 0 选 y − 1，不会等于 0。 -- **判别式递推**（第 5 节）：d 初值 `1 - r`。d < 0 时 `d += 2x + 3`，y 不变。否则 `d += 2(x - y) + 5`，y 减 1。循环里只剩加减法和比较。 -- **Follow-up**：圆心是整数坐标就整体平移。涂满时每一行从最左到最右的圆周像素涂满。用 C 写时第五版的 d 始终在 4r + 4 以内，不会像 `r * r` 那样在 r = 46341 溢出。 -- **原帖说不清的两处**（第 3、6 节）：「x 从 r 变到 0.717r 多画几个点」字面上和「y 只会不变或减 1」矛盾。「最终只用了一次乘法」具体怎么写，没人答过。 +- **题**（题目一节）：圆心在原点、半径整数 r，用 `plot(x, y)` 画圆周，考的是优化链，先问清表里几点。 +- **只画圆上整点不行**（思路第 1 节）：r = 3 只有 $(0, \pm 3)$、$(\pm 3, 0)$ 四点，follow-up「r 小时多画点」因此而来。 +- **每列取最近整数会断**（第 2 节）：靠近 $(\pm r, 0)$ 圆很陡，y 一次掉好几格，每列一个点就空了。 +- **只算 0° 到 45° 再 8 路对称**（第 3 节）：相邻两列高度差小于 1，y 只会不变或减 1，不断，循环写 `x <= y`。 +- **不开方**（第 4 节）：中点代入 $x^2 + y^2 - r^2$，小于 0 选 y，大于 0 选 $y - 1$，不会是 0。 +- **判别式递推**（第 5 节）：d 初值 `1 - r`，小于 0 则 `d += 2x + 3`，否则 `d += 2(x - y) + 5`、y 减 1，循环只剩加减比较。 +- **Follow-up**（1 到 3）：整数圆心就平移，涂满按行从最左涂到最右圆周像素，C 里 d 不超过 $4r + 4$，不像 `r * r` 在 r = 46341 溢出。 +- **原帖说不清的两处**（第 3、6 节）：「x 从 r 变到 0.717r 多画几个点」与「y 只会不变或减 1」矛盾，「一次乘法」怎么写没人答。 ## 题目 @@ -14,5 +14,5 @@ 站内三条面经来源（下一节）都没写题面。下面的题面来自一份二手题目汇总（公开的 Google 文档，站内登记为 gdoc:purestorage-notes，没有日期，也查不到是谁的面经）：圆心在原点 (0, 0)，半径是 R，给你一个现成的函数 `plot(x, y)`，要求把圆画出来。本页把半径写成 r。 -先讲一点图形学（computer graphics）的基础，后面都要用。屏幕是一张整数网格，每个格子叫一个像素（pixel），`plot(x, y)` 只能点亮整数坐标 (x, y)。真实的圆是满足 x² + y² = r² 的所有点，其中绝大多数不是整数，所以「画圆」的意思是挑出一批离圆最近的像素点亮，让它们看上去连成一圈。本页的标准是：以两条对角线 y = x、y = −x 为界，圆顶和圆底那两块比较平，每一列 x 取离圆最近的那个整数 y。左右两块比较陡，每一行 y 取离圆最近的那个整数 x（为什么要这样分，思路第 2、3 节讲）。每个像素只 `plot` 一次。r = 0 时只画圆心 (0, 0)。 +先讲一点图形学（computer graphics）的基础，后面都要用。屏幕是一张整数网格，每个格子叫一个像素（pixel），`plot(x, y)` 只能点亮整数坐标 (x, y)。真实的圆是满足 $x^2 + y^2 = r^2$ 的所有点，其中绝大多数不是整数，所以「画圆」的意思是挑出一批离圆最近的像素点亮，让它们看上去连成一圈。本页的标准是：以两条对角线 $y = x$、$y = -x$ 为界，圆顶和圆底那两块比较平，每一列 x 取离圆最近的那个整数 y。左右两块比较陡，每一行 y 取离圆最近的那个整数 x（为什么要这样分，思路第 2、3 节讲）。每个像素只 `plot` 一次。r = 0 时只画圆心 (0, 0)。 r = 3 时按这个标准画出来是 16 个像素。下图里 `#` 是点亮的像素，`+` 是圆心，向右是 x 增大，向上是 y 增大： @@ -28,5 +28,5 @@ ``` -这 16 个点是 (0, ±3)、(±3, 0)、(±1, ±3)、(±3, ±1)、(±2, ±2)。它们离圆心的距离是 3、√10 ≈ 3.162、√8 ≈ 2.828，离真实的圆都不到 0.2 格。 +这 16 个点是 $(0, \pm 3)$、$(\pm 3, 0)$、$(\pm 1, \pm 3)$、$(\pm 3, \pm 1)$、$(\pm 2, \pm 2)$。它们离圆心的距离是 3、$\sqrt{10} \approx 3.162$、$\sqrt{8} \approx 2.828$，离真实的圆都不到 0.2 格。 ### 开写之前要问清楚的 @@ -49,5 +49,5 @@ - **2026-09，一亩三分地 [1189219](https://www.1point3acres.com/interview/thread/1189219)**。标题写的是 pre-screen，正文说是 onsite，网站按 onsite 记，到底是哪一轮查不到。发帖人说画圆是「祖传 coding 之一」，他没提前看过，在面试官的各种提示下写完了。这次面试的另一轮是 [[q:everpure-fire-event]]。面完第二天收到拒信，理由是 not match。他的感受是这家看重沟通和现场反应。 - **2025-10，Jointaro 上一篇 Senior SDE（美国）面经**。只在题目清单里写了「drawing circle」，和另外两道题并列，没说在哪一轮、怎么问的。结果页面自相矛盾（标的是 No Offer，正文又说最后有 offer call）。 -- **题目一节那份二手题目汇总**里有两段，出处都没注明。一段说：朴素做法是 x 从 0 到 R/√2，用 y = √(R² − x²) 算 y，再做 8 路对称。follow-up 是像素不连续，怎么让圆连起来，面试官介绍了 Bresenham 画圆算法（就是下面第 5 节）。最后去掉 sqrt，循环条件换成 `x <= y`。作者也说做得磕绊，面试官给了不少提示。另一段要求不用 sqrt、sin、cos，提示是所有点都是整点，0° 到 45° 内 x 加 1 时 y 不变或减 1，代进圆方程看哪个对。这份文档列的 8 个对称点有抄写错误（`plot(y, x)` 写了两遍，漏了 `plot(y, -x)`），不要照抄，正确的列表见第 3 节。文档开头说「可能需要用数学方法证明解法的正确性」，对照 192327 原帖，那句说的是电话面试里的 Happy Number，不是画圆。画圆要不要证明，没有原话。 +- **题目一节那份二手题目汇总**里有两段，出处都没注明。一段说：朴素做法是 x 从 0 到 $R/\sqrt{2}$，用 $y = \sqrt{R^2 - x^2}$ 算 y，再做 8 路对称。follow-up 是像素不连续，怎么让圆连起来，面试官介绍了 Bresenham 画圆算法（就是下面第 5 节）。最后去掉 sqrt，循环条件换成 `x <= y`。作者也说做得磕绊，面试官给了不少提示。另一段要求不用 sqrt、sin、cos，提示是所有点都是整点，0° 到 45° 内 x 加 1 时 y 不变或减 1，代进圆方程看哪个对。这份文档列的 8 个对称点有抄写错误（`plot(y, x)` 写了两遍，漏了 `plot(y, -x)`），不要照抄，正确的列表见第 3 节。文档开头说「可能需要用数学方法证明解法的正确性」，对照 192327 原帖，那句说的是电话面试里的 Happy Number，不是画圆。画圆要不要证明，没有原话。 - **教训**：「画圆」这个题名至少从 2016 年出现到 2026 年。只有 2016 年那篇写了 follow-up，后两篇都没写题面和追问，是否和 2016 年一样，查不到。按 2016 年那篇，起点几分钟就写完，分数在后面的优化链上，面试官会一步一步引导。2026 年那篇也说是在面试官的提示下写完的。要能自己说出每一步为什么对（第 3 节的高度差论证、第 5 节的判别式推导）。 @@ -56,5 +56,5 @@ ### 1. 第一版：只画恰好在圆上的整点 -最直接的理解是：「圆上的点」就是满足 x² + y² = r² 的整数点。x 从 0 到 r 循环，算出 y，是整数才画，再上下左右对称。原帖没写最初的代码，但「孤零零的四个点」正好是这一版在 r = 3 时的结果，所以起点很可能就是这样【推断】。 +最直接的理解是：「圆上的点」就是满足 $x^2 + y^2 = r^2$ 的整数点。x 从 0 到 r 循环，算出 y，是整数才画，再上下左右对称。原帖没写最初的代码，但「孤零零的四个点」正好是这一版在 r = 3 时的结果，所以起点很可能就是这样【推断】。 ```python @@ -71,9 +71,9 @@ ``` -r = 3 时 9 只能拆成 0 + 9（1 + 8、4 + 5 都不是两个平方数的和），所以只有 (0, ±3)、(±3, 0) 四个点。r = 5 好一些，因为 25 = 9 + 16，多出 (±3, ±4)、(±4, ±3)，一共 12 个点，但圆周上还是大片空白。整点有几个，取决于 r² 能拆成几种平方和，和圆周有多长不成比例：r = 7 时也只有 4 个。所以这不是画圆的办法。follow-up「r 很小时多画几个点」就是让你放弃「恰好在圆上」，改成「离圆最近」。 +r = 3 时 9 只能拆成 0 + 9（1 + 8、4 + 5 都不是两个平方数的和），所以只有 $(0, \pm 3)$、$(\pm 3, 0)$ 四个点。r = 5 好一些，因为 $25 = 9 + 16$，多出 $(\pm 3, \pm 4)$、$(\pm 4, \pm 3)$，一共 12 个点，但圆周上还是大片空白。整点有几个，取决于 $r^2$ 能拆成几种平方和，和圆周有多长不成比例：r = 7 时也只有 4 个。所以这不是画圆的办法。follow-up「r 很小时多画几个点」就是让你放弃「恰好在圆上」，改成「离圆最近」。 ### 2. 第二版：每一列取离圆最近的整数 -对每个整数 x，圆在这一列的真实高度是 Y(x) = √(r² − x²)，取离它最近的整数 y = round(Y(x))。Y(x) 不会恰好是「整数 + ½」：(k + ½)² = k² + k + ¼ 不是整数，而 Y(x)² = r² − x² 是整数。所以 Python 的 `round` 遇到 .5 怎么取舍，这里碰不到。 +对每个整数 x，圆在这一列的真实高度是 $Y(x) = \sqrt{r^2 - x^2}$，取离它最近的整数 $y = \operatorname{round}(Y(x))$。$Y(x)$ 不会恰好是「整数 + $\tfrac{1}{2}$」：$(k + \tfrac{1}{2})^2 = k^2 + k + \tfrac{1}{4}$ 不是整数，而 $Y(x)^2 = r^2 - x^2$ 是整数。所以 Python 的 `round` 遇到 .5 怎么取舍，这里碰不到。 ```python @@ -87,5 +87,5 @@ ``` -r = 3 时得到 (0, ±3)、(±1, ±3)、(±2, ±2)、(±3, 0)，12 个点。但 (±3, ±1) 没画上：x = 2 时 y = 2，x = 3 时 y = 0，中间 y = 1 那格跳过了，圆在左右两端断开。r = 5 时更明显，左边是第二版，右边是第 5 节的最终版： +r = 3 时得到 $(0, \pm 3)$、$(\pm 1, \pm 3)$、$(\pm 2, \pm 2)$、$(\pm 3, 0)$，12 个点。但 $(\pm 3, \pm 1)$ 没画上：x = 2 时 y = 2，x = 3 时 y = 0，中间 y = 1 那格跳过了，圆在左右两端断开。r = 5 时更明显，左边是第二版，右边是第 5 节的最终版： ```text @@ -104,5 +104,5 @@ ``` -第二版在 x = 4 到 x = 5 之间，y 从 3 直接掉到 0，(5, ±1)、(5, ±2) 和左边对应的点都没画。上下两端却是好的。 +第二版在 x = 4 到 x = 5 之间，y 从 3 直接掉到 0，$(5, \pm 1)$、$(5, \pm 2)$ 和左边对应的点都没画。上下两端却是好的。 原因在斜率（slope）。这里说的斜率是圆的切线斜率，直观地说就是 x 加 1 时圆的高度变多少。圆顶附近（x 小）很平，x 加 1 时 Y 几乎不变。越往 (r, 0) 走越陡，到最右端几乎是竖直的，x 加 1 时 Y 一下掉好几格，而每一列只画一个点，掉下去的那几格就空着。 @@ -110,7 +110,7 @@ ### 3. 第三版：只算平的那八分之一，再 8 路对称 -把圆用 x 轴、y 轴和两条对角线 y = x、y = −x 切成 8 段，每段 45°，叫八分之一圆（octant）。只算从圆顶 (0, r) 到对角线 y = x 的那一段，它满足 0 ≤ x ≤ y。其他 7 段都能由它镜像得到：(x, y) 关于 y 轴镜像是 (−x, y)，关于 x 轴是 (x, −y)，关于对角线 y = x 是 (y, x)。三种镜像组合起来正好 8 个点： - -(x, y)、(y, x)、(−x, y)、(−y, x)、(x, −y)、(y, −x)、(−x, −y)、(−y, −x) +把圆用 x 轴、y 轴和两条对角线 $y = x$、$y = -x$ 切成 8 段，每段 45°，叫八分之一圆（octant）。只算从圆顶 (0, r) 到对角线 $y = x$ 的那一段，它满足 $0 \le x \le y$。其他 7 段都能由它镜像得到：$(x, y)$ 关于 y 轴镜像是 $(-x, y)$，关于 x 轴是 $(x, -y)$，关于对角线 $y = x$ 是 $(y, x)$。三种镜像组合起来正好 8 个点： + +$(x, y)$、$(y, x)$、$(-x, y)$、$(-y, x)$、$(x, -y)$、$(y, -x)$、$(-x, -y)$、$(-y, -x)$ ```python @@ -131,31 +131,33 @@ ``` -这一段不会断，是因为相邻两列的真实高度差可以不开方地写出来（分子是 (r² − (x − 1)²) − (r² − x²) = 2x − 1）： - -Y(x − 1) − Y(x) = (Y(x − 1)² − Y(x)²) / (Y(x − 1) + Y(x)) = (2x − 1) / (Y(x − 1) + Y(x)) - -循环只处理像素 y ≥ x 的列，而像素 y 是 Y(x) 取整来的，所以这些列满足 Y(x) ≥ x − ½。再加上 Y(x − 1) > Y(x)，分母 > 2Y(x) ≥ 2x − 1，所以高度差小于 1。真实高度差小于 1，取整以后的 y 最多差 1：round(a) − round(b) < (a + ½) − (b − ½) < 2，又是整数，所以不超过 1。也就是说 x 每加 1，y 要么不变，要么减 1，相邻两列总是横着或斜着挨着，不会有空格。这就是发帖人说的「这段范围内圆的斜率小于 1」。镜像以后各段的接头也挨着。8 个接头都是两种接头的镜像：圆顶那头，(0, r) 和左右两边第 1 列的像素横着或斜着挨着。对角线那头，记这一段最后一个像素为 (x_end, y_end)，它满足 y_end − x_end ≤ 1。反证：如果 y_end ≥ x_end + 2，那么 Y(x_end) > y_end − ½ ≥ x_end + 3/2，下一列 Y(x_end + 1)² = Y(x_end)² − 2x_end − 1 > (x_end + 3/2)² − 2x_end − 1 = (x_end + ½)² + 1，所以 Y(x_end + 1) > x_end + ½，取整后至少是 x_end + 1，下一列还在这一段里，和「最后一个」矛盾。于是 (x_end, y_end) 和它关于对角线的镜像 (y_end, x_end) 两个坐标都只差 0 或 1，也挨着。整圈连通（每个像素和周围 8 格里的像素算相连，这叫 8 连通）的逐个检查见测试用例。 - -r = 3 时这一段是 (0, 3)、(1, 3)、(2, 2)，镜像出 4 + 8 + 4 = 16 个点，就是题目一节的图，比第二版多出第二版漏掉的 (±3, ±1) 四个点。 +这一段不会断，是因为相邻两列的真实高度差可以不开方地写出来（分子是 $(r^2 - (x - 1)^2) - (r^2 - x^2) = 2x - 1$）： + +$$ +Y(x - 1) - Y(x) = \frac{Y(x - 1)^2 - Y(x)^2}{Y(x - 1) + Y(x)} = \frac{2x - 1}{Y(x - 1) + Y(x)} +$$ + +循环只处理像素 $y \ge x$ 的列，而像素 y 是 $Y(x)$ 取整来的，所以这些列满足 $Y(x) \ge x - \tfrac{1}{2}$。再加上 $Y(x - 1) > Y(x)$，分母 $> 2Y(x) \ge 2x - 1$，所以高度差小于 1。真实高度差小于 1，取整以后的 y 最多差 1：$\operatorname{round}(a) - \operatorname{round}(b) < (a + \tfrac{1}{2}) - (b - \tfrac{1}{2}) < 2$，又是整数，所以不超过 1。也就是说 x 每加 1，y 要么不变，要么减 1，相邻两列总是横着或斜着挨着，不会有空格。这就是发帖人说的「这段范围内圆的斜率小于 1」。镜像以后各段的接头也挨着。8 个接头都是两种接头的镜像：圆顶那头，(0, r) 和左右两边第 1 列的像素横着或斜着挨着。对角线那头，记这一段最后一个像素为 $(x_{\text{end}}, y_{\text{end}})$，它满足 $y_{\text{end}} - x_{\text{end}} \le 1$。反证：如果 $y_{\text{end}} \ge x_{\text{end}} + 2$，那么 $Y(x_{\text{end}}) > y_{\text{end}} - \tfrac{1}{2} \ge x_{\text{end}} + \tfrac{3}{2}$，下一列 $Y(x_{\text{end}} + 1)^2 = Y(x_{\text{end}})^2 - 2x_{\text{end}} - 1 > (x_{\text{end}} + \tfrac{3}{2})^2 - 2x_{\text{end}} - 1 = (x_{\text{end}} + \tfrac{1}{2})^2 + 1$，所以 $Y(x_{\text{end}} + 1) > x_{\text{end}} + \tfrac{1}{2}$，取整后至少是 $x_{\text{end}} + 1$，下一列还在这一段里，和「最后一个」矛盾。于是 $(x_{\text{end}}, y_{\text{end}})$ 和它关于对角线的镜像 $(y_{\text{end}}, x_{\text{end}})$ 两个坐标都只差 0 或 1，也挨着。整圈连通（每个像素和周围 8 格里的像素算相连，这叫 8 连通）的逐个检查见测试用例。 + +r = 3 时这一段是 (0, 3)、(1, 3)、(2, 2)，镜像出 4 + 8 + 4 = 16 个点，就是题目一节的图，比第二版多出第二版漏掉的 $(\pm 3, \pm 1)$ 四个点。 #### 终止条件 -二手资料的朴素写法是 x 从 0 循环到 R/√2，要先算一次 √2，或者每步比较 2x² 和 r²。直接判断「像素走过对角线没有」（x > y 就停）省掉了这次计算，这就是发帖人说的「终止条件写成 `x < y`，少用一次乘法或开方」。不过写成 `while x < y` 会漏掉 x 恰好等于 y 的那一列：r = 3 时循环走到 (2, 2) 就停了，(±2, ±2) 四个点没画。要写 `x <= y`。 +二手资料的朴素写法是 x 从 0 循环到 $R/\sqrt{2}$，要先算一次 $\sqrt{2}$，或者每步比较 $2x^2$ 和 $r^2$。直接判断「像素走过对角线没有」（$x > y$ 就停）省掉了这次计算，这就是发帖人说的「终止条件写成 `x < y`，少用一次乘法或开方」。不过写成 `while x < y` 会漏掉 x 恰好等于 y 的那一列：r = 3 时循环走到 (2, 2) 就停了，$(\pm 2, \pm 2)$ 四个点没画。要写 `x <= y`。 #### 原帖里矛盾的一句 -192327 还写了「x 从 r 变到 0.717r 要比从 0 变到 0.717r 可以多画几个点」。0.717 多半是 1/√2 ≈ 0.707 的笔误【推断】。照字面理解，x 从 0.707r 到 r 是靠近 (r, 0) 的那段陡弧，正是第二版断开的地方，在那里让 x 每次加 1 只会画出更少的点。r = 10 时，x 从 0 到 7 的那段平弧有 8 列。x 从 7 到 10 的那段陡弧弧长一样（都是 45°），却只有 4 列，y 依次是 7、6、4、0，从 4 直接跳到 0。所以字面意思和同帖「y 只会不变或减 1，因为斜率小于 1」对不上。帖子下有两个人问过这句什么意思，发帖人没有回答，原意查不到。本页按 x 从 0 到 r/√2 讲。面试时如果面试官提到这一句，直接问他指的是哪一段。 +192327 还写了「x 从 r 变到 0.717r 要比从 0 变到 0.717r 可以多画几个点」。0.717 多半是 $1/\sqrt{2} \approx 0.707$ 的笔误【推断】。照字面理解，x 从 0.707r 到 r 是靠近 (r, 0) 的那段陡弧，正是第二版断开的地方，在那里让 x 每次加 1 只会画出更少的点。r = 10 时，x 从 0 到 7 的那段平弧有 8 列。x 从 7 到 10 的那段陡弧弧长一样（都是 45°），却只有 4 列，y 依次是 7、6、4、0，从 4 直接跳到 0。所以字面意思和同帖「y 只会不变或减 1，因为斜率小于 1」对不上。帖子下有两个人问过这句什么意思，发帖人没有回答，原意查不到。本页按 x 从 0 到 $r/\sqrt{2}$ 讲。面试时如果面试官提到这一句，直接问他指的是哪一段。 ### 4. 第四版：不开方，比较两个候选 -第 3 节已经证明：从第 x 列走到第 x + 1 列，y 只有两个候选，y 本身或者 y − 1。所以不需要算 √，只要判断哪个离圆更近。 - -方法是看两个候选的中点 (x + 1, y − ½)。定义 f(x, y) = x² + y² − r²：点在圆内 f < 0，在圆上 f = 0，在圆外 f > 0。 - -- **f(x + 1, y − ½) < 0**：中点在圆内，说明圆在这一列经过的位置比中点高，离上面的候选更近，选 y。 -- **f(x + 1, y − ½) > 0**：中点在圆外，圆经过的位置比中点低，选 y − 1。 -- **不会等于 0**：f 乘 4 是 4(x + 1)² + (2y − 1)² − 4r²，其中 (2y − 1)² 是奇数的平方，除以 4 余 1，另外两项都是 4 的倍数，总和除以 4 余 1，不可能是 0。 - -「看中点」就等于「选最近的」，原因是：中点在圆内，即 (x + 1)² + (y − ½)² < r²，即 (y − ½)² < Y(x + 1)²，两边都是正数，所以 y − ½ < Y(x + 1)。另一边 Y(x + 1) ≤ Y(x) < y + ½。Y(x + 1) 落在 y ± ½ 之间，最近的整数就是 y。中点在圆外时，Y(x + 1) < y − ½。再由第 3 节的高度差小于 1，Y(x + 1) > Y(x) − 1 ≥ y − 3/2，最近的整数是 y − 1。不过第 3 节的高度差论证只对还没越过对角线的列成立，所以还要确认第 x + 1 列在这一段里。如果 x ≤ y − 2，第 3 节接头论证里的反证已经算过 Y(x + 1) > x + ½，第 x + 1 列确实还在这一段里。剩下 x ≥ y − 1 的情况：中点在圆外时，第四版选 y − 1 < x + 1，第三版算出的 round(Y(x + 1)) ≤ y − 1 < x + 1，两版都在这一列停下、不画它。所以第四版和第三版画出的像素完全一样。这是逐列归纳：起点 (0, r) 两版相同。上面用到的 y − ½ < Y(x) < y + ½，就是归纳假设「第 x 列两版相同，都是离 Y(x) 最近的整数」。 +第 3 节已经证明：从第 x 列走到第 x + 1 列，y 只有两个候选，y 本身或者 $y - 1$。所以不需要算 √，只要判断哪个离圆更近。 + +方法是看两个候选的中点 $(x + 1, y - \tfrac{1}{2})$。定义 $f(x, y) = x^2 + y^2 - r^2$：点在圆内 $f < 0$，在圆上 $f = 0$，在圆外 $f > 0$。 + +- **$f(x + 1, y - \tfrac{1}{2}) < 0$**：中点在圆内，说明圆在这一列经过的位置比中点高，离上面的候选更近，选 y。 +- **$f(x + 1, y - \tfrac{1}{2}) > 0$**：中点在圆外，圆经过的位置比中点低，选 $y - 1$。 +- **不会等于 0**：f 乘 4 是 $4(x + 1)^2 + (2y - 1)^2 - 4r^2$，其中 $(2y - 1)^2$ 是奇数的平方，除以 4 余 1，另外两项都是 4 的倍数，总和除以 4 余 1，不可能是 0。 + +「看中点」就等于「选最近的」，原因是：中点在圆内，即 $(x + 1)^2 + (y - \tfrac{1}{2})^2 < r^2$，即 $(y - \tfrac{1}{2})^2 < Y(x + 1)^2$，两边都是正数，所以 $y - \tfrac{1}{2} < Y(x + 1)$。另一边 $Y(x + 1) \le Y(x) < y + \tfrac{1}{2}$。$Y(x + 1)$ 落在 $y \pm \tfrac{1}{2}$ 之间，最近的整数就是 y。中点在圆外时，$Y(x + 1) < y - \tfrac{1}{2}$。再由第 3 节的高度差小于 1，$Y(x + 1) > Y(x) - 1 \ge y - \tfrac{3}{2}$，最近的整数是 $y - 1$。不过第 3 节的高度差论证只对还没越过对角线的列成立，所以还要确认第 x + 1 列在这一段里。如果 $x \le y - 2$，第 3 节接头论证里的反证已经算过 $Y(x + 1) > x + \tfrac{1}{2}$，第 x + 1 列确实还在这一段里。剩下 $x \ge y - 1$ 的情况：中点在圆外时，第四版选 $y - 1 < x + 1$，第三版算出的 $\operatorname{round}(Y(x + 1)) \le y - 1 < x + 1$，两版都在这一列停下、不画它。所以第四版和第三版画出的像素完全一样。这是逐列归纳：起点 (0, r) 两版相同。上面用到的 $y - \tfrac{1}{2} < Y(x) < y + \tfrac{1}{2}$，就是归纳假设「第 x 列两版相同，都是离 $Y(x)$ 最近的整数」。 ```python @@ -173,5 +175,5 @@ ``` -这一版没有开方了，但每一列还要算 x·x 和 (2y − 1)² 两次乘法（4r² 可以在循环外算好）。 +这一版没有开方了，但每一列还要算 $x \cdot x$ 和 $(2y - 1)^2$ 两次乘法（$4r^2$ 可以在循环外算好）。 ### 5. 第五版：判别式递推，循环里只剩加减法 @@ -179,17 +181,23 @@ 第四版每一列都从头算一遍 f。其实相邻两列的 f 只差一点，可以从上一列的值加出来。这就是中点画圆法（midpoint circle algorithm），也常叫 Bresenham 画圆法，二手资料里说的就是它。 -先命名：当前像素记作 (x, y)。判断下一列用的中点是 (x + 1, y − ½)，它的 f 值记作 P，也就是 P = f(x + 1, y − ½)。P 叫判别式（decision variable），因为它的正负决定下一步怎么走。下面分三步推 P 怎么变。 - -先求初值。第一个像素是圆顶 (0, r)，所以 P = f(1, r − ½) = 1 + (r − ½)² − r² = 1 + r² − r + ¼ − r² = 5/4 − r。 - -P < 0 时下一列选 y。新像素是 (x + 1, y)，下一次要看的中点是 (x + 2, y − ½)。和旧中点 (x + 1, y − ½) 比，只有横坐标多了 1，所以新的 P = 旧的 P + (x + 2)² − (x + 1)² = 旧的 P + 2x + 3。 - -P > 0 时下一列选 y − 1。新像素是 (x + 1, y − 1)，下一次的中点是 (x + 2, y − 3/2)。横坐标多 1，纵坐标少 1，两部分各算各的： - -新的 P = 旧的 P + [(x + 2)² − (x + 1)²] + [(y − 3/2)² − (y − ½)²] = 旧的 P + (2x + 3) + (−2y + 2) = 旧的 P + 2(x − y) + 5 +先命名：当前像素记作 (x, y)。判断下一列用的中点是 $(x + 1, y - \tfrac{1}{2})$，它的 f 值记作 P，也就是 $P = f(x + 1, y - \tfrac{1}{2})$。P 叫判别式（decision variable），因为它的正负决定下一步怎么走。下面分三步推 P 怎么变。 + +先求初值。第一个像素是圆顶 (0, r)，所以 $P = f(1, r - \tfrac{1}{2}) = 1 + (r - \tfrac{1}{2})^2 - r^2 = 1 + r^2 - r + \tfrac{1}{4} - r^2 = \tfrac{5}{4} - r$。 + +$P < 0$ 时下一列选 y。新像素是 $(x + 1, y)$，下一次要看的中点是 $(x + 2, y - \tfrac{1}{2})$。和旧中点 $(x + 1, y - \tfrac{1}{2})$ 比，只有横坐标多了 1，所以 $\text{新的 } P = \text{旧的 } P + (x + 2)^2 - (x + 1)^2 = \text{旧的 } P + 2x + 3$。 + +$P > 0$ 时下一列选 $y - 1$。新像素是 $(x + 1, y - 1)$，下一次的中点是 $(x + 2, y - \tfrac{3}{2})$。横坐标多 1，纵坐标少 1，两部分各算各的： + +$$ +\begin{aligned} +\text{新的 } P &= \text{旧的 } P + [(x + 2)^2 - (x + 1)^2] + [(y - \tfrac{3}{2})^2 - (y - \tfrac{1}{2})^2] \\ +&= \text{旧的 } P + (2x + 3) + (-2y + 2) \\ +&= \text{旧的 } P + 2(x - y) + 5 +\end{aligned} +$$ 两个式子里的 x、y 都是更新之前的值，所以代码里要先改 P，再改 x、y。 -再把 ¼ 去掉。两个增量 2x + 3 和 2(x − y) + 5 都是整数，r 是整数时只有初值 5/4 − r 带分数，所以 P 永远是「某个整数 + ¼」。令 d = P − ¼，d 就始终是整数，初值 1 − r，增量不变。判断也不受影响：P < 0 等价于 d < −¼，d 是整数，所以等价于 d < 0。反过来 P > 0 等价于 d ≥ 0。另一种办法是全部乘 4：初值 5 − 4r，两个增量变成 8x + 12 和 8(x − y) + 20，结果一样。二手资料说的「误差累积到阈值就修正」，对应的就是 d 一路加上来，越过 0 时把 y 减 1。 +再把 $\tfrac{1}{4}$ 去掉。两个增量 $2x + 3$ 和 $2(x - y) + 5$ 都是整数，r 是整数时只有初值 $\tfrac{5}{4} - r$ 带分数，所以 P 永远是「某个整数 + $\tfrac{1}{4}$」。令 $d = P - \tfrac{1}{4}$，d 就始终是整数，初值 $1 - r$，增量不变。判断也不受影响：$P < 0$ 等价于 $d < -\tfrac{1}{4}$，d 是整数，所以等价于 $d < 0$。反过来 $P > 0$ 等价于 $d \ge 0$。另一种办法是全部乘 4：初值 $5 - 4r$，两个增量变成 $8x + 12$ 和 $8(x - y) + 20$，结果一样。二手资料说的「误差累积到阈值就修正」，对应的就是 d 一路加上来，越过 0 时把 y 减 1。 用 r = 5 走一遍（d 是判断下一列用的值）： @@ -197,14 +205,14 @@ | 步 | 当前像素 (x, y) | d | 判断 | 下一列 | d 的更新 | | --- | --- | --- | --- | --- | --- | -| 1 | (0, 5) | −4 | d < 0，y 不变 | (1, 5) | −4 + (2·0 + 3) = −1 | -| 2 | (1, 5) | −1 | d < 0，y 不变 | (2, 5) | −1 + (2·1 + 3) = 4 | -| 3 | (2, 5) | 4 | d ≥ 0，y 减 1 | (3, 4) | 4 + (2·(2 − 5) + 5) = 3 | -| 4 | (3, 4) | 3 | d ≥ 0，y 减 1 | (4, 3) | 3 + (2·(3 − 4) + 5) = 6 | - -第 4 步之后 x = 4 > y = 3，循环结束。(4, 3) 不属于这一段，它是 (3, 4) 关于对角线的镜像，已经画过了。核对一下：Y(1) = √24 ≈ 4.90，Y(2) = √21 ≈ 4.58，Y(3) = 4，取整都和表里一致。每一步的 d 也都等于 f(x + 1, y − ½) − ¼，比如第 3 步 f(3, 4.5) = 9 + 20.25 − 25 = 4.25，减 ¼ 是 4。完整代码见代码一节。 +| 1 | (0, 5) | $-4$ | $d < 0$，y 不变 | (1, 5) | $-4 + (2 \cdot 0 + 3) = -1$ | +| 2 | (1, 5) | $-1$ | $d < 0$，y 不变 | (2, 5) | $-1 + (2 \cdot 1 + 3) = 4$ | +| 3 | (2, 5) | 4 | $d \ge 0$，y 减 1 | (3, 4) | $4 + (2 \cdot (2 - 5) + 5) = 3$ | +| 4 | (3, 4) | 3 | $d \ge 0$，y 减 1 | (4, 3) | $3 + (2 \cdot (3 - 4) + 5) = 6$ | + +第 4 步之后 x = 4 > y = 3，循环结束。(4, 3) 不属于这一段，它是 (3, 4) 关于对角线的镜像，已经画过了。核对一下：$Y(1) = \sqrt{24} \approx 4.90$，$Y(2) = \sqrt{21} \approx 4.58$，$Y(3) = 4$，取整都和表里一致。每一步的 d 也都等于 $f(x + 1, y - \tfrac{1}{2}) - \tfrac{1}{4}$，比如第 3 步 $f(3, 4.5) = 9 + 20.25 - 25 = 4.25$，减 $\tfrac{1}{4}$ 是 4。完整代码见代码一节。 #### r 不是整数时 -「P 永远是整数 + ¼」要求 r 是整数。r 不是整数时 d 不再是整数，「d < 0 等价于 P < 0」也就不成立。反例 r = 1.1：起点取离 r 最近的整数 1，P = f(1, ½) = 1 + ¼ − 1.21 = 0.04 > 0，中点在圆外，该把 y 减 1。d = P − ¼ = −0.21 < 0，却判成 y 不变，于是画出 (1, 1)，而 Y(1) = √0.21 ≈ 0.46，最近的整数是 0。改法是不减 ¼，直接维护 P：初值 1 + (y₀ − ½)² − r²（y₀ 是离 r 最近的整数），按 P < 0 判断。两个增量不变，因为推导增量时 r² 消掉了。这时 P 可能恰好是 0（r = 2.5 时起点取 2，走到 (1, 2)，中点 (2, 1.5) 正好在圆上），两个候选一样近，选哪个都行。r 是「整数 + ½」时起点的 y₀ 本身也是两个一样近，同样任选。 +「P 永远是整数 + $\tfrac{1}{4}$」要求 r 是整数。r 不是整数时 d 不再是整数，「$d < 0$ 等价于 $P < 0$」也就不成立。反例 r = 1.1：起点取离 r 最近的整数 1，$P = f(1, \tfrac{1}{2}) = 1 + \tfrac{1}{4} - 1.21 = 0.04 > 0$，中点在圆外，该把 y 减 1。$d = P - \tfrac{1}{4} = -0.21 < 0$，却判成 y 不变，于是画出 (1, 1)，而 $Y(1) = \sqrt{0.21} \approx 0.46$，最近的整数是 0。改法是不减 $\tfrac{1}{4}$，直接维护 P：初值 $1 + (y_0 - \tfrac{1}{2})^2 - r^2$（$y_0$ 是离 r 最近的整数），按 $P < 0$ 判断。两个增量不变，因为推导增量时 $r^2$ 消掉了。这时 P 可能恰好是 0（r = 2.5 时起点取 2，走到 (1, 2)，中点 (2, 1.5) 正好在圆上），两个候选一样近，选哪个都行。r 是「整数 + $\tfrac{1}{2}$」时起点的 $y_0$ 本身也是两个一样近，同样任选。 ### 6. 「最终只用了一次乘法」指什么 @@ -212,13 +220,13 @@ 发帖人说最终版只用了一次乘法，面试官才满意。帖子没贴代码。2017 年有人在评论里问「中点法每一步也要一次乘法，怎么能一共只用一次」，没人回答，所以他的代码长什么样查不到。 -把几版的运算量列出来（乘以 2、乘以 4 这类常数不算，因为 2x 就是 x + x 或者 x << 1，只是一次加法或移位。r·r 可以提到循环外）： +把几版的运算量列出来（乘以 2、乘以 4 这类常数不算，因为 2x 就是 x + x 或者 x << 1，只是一次加法或移位。$r \cdot r$ 可以提到循环外）： | 版本 | 每一列开方 | 每一列乘法 | | --- | --- | --- | -| 第二、三版 | 1 次 | 1 次（x·x） | -| 第四版 | 0 | 2 次（x·x 和 (2y − 1)²） | +| 第二、三版 | 1 次 | 1 次（$x \cdot x$） | +| 第四版 | 0 | 2 次（$x \cdot x$ 和 $(2y - 1)^2$） | | 第五版 | 0 | 0 | -第五版的循环里没有真正的乘法，初值 1 − r 也不用乘法。发帖人的「一次」可能是在循环外算了一次 r·r（比如他维护的是 x² + y² − r² 本身），也可能是循环里还剩一次【推断】。无论是哪种，第五版都不比它多。面试官问「还能不能更少」时，可以说循环里已经没有乘法了，再讲第 5 节的推导。 +第五版的循环里没有真正的乘法，初值 $1 - r$ 也不用乘法。发帖人的「一次」可能是在循环外算了一次 $r \cdot r$（比如他维护的是 $x^2 + y^2 - r^2$ 本身），也可能是循环里还剩一次【推断】。无论是哪种，第五版都不比它多。面试官问「还能不能更少」时，可以说循环里已经没有乘法了，再讲第 5 节的推导。 ## 代码 @@ -248,10 +256,10 @@ ``` -`mirror8` 返回集合，是为了去掉重合的点：x = 0 时 (x, y) 和 (−x, y) 是同一个点，x = y 时 (x, y) 和 (y, x) 是同一个点，r = 0 时 8 个点全是 (0, 0)。不同的列之间不会重复：8 个对称点的坐标取绝对值以后，都是 x、y 这两个数（顺序可能对调），所以两列 x₁ < x₂ 要重复，只能是 (y₁, x₁) = (x₂, y₂)，那么 y₂ = x₁ < x₂，和这一段里 x₂ ≤ y₂ 矛盾。用 C 写没有集合时，就在 x = 0 和 x = y 时各只画 4 个点，r = 0 单独处理。 +`mirror8` 返回集合，是为了去掉重合的点：x = 0 时 $(x, y)$ 和 $(-x, y)$ 是同一个点，x = y 时 $(x, y)$ 和 $(y, x)$ 是同一个点，r = 0 时 8 个点全是 (0, 0)。不同的列之间不会重复：8 个对称点的坐标取绝对值以后，都是 x、y 这两个数（顺序可能对调），所以两列 $x_1 < x_2$ 要重复，只能是 $(y_1, x_1) = (x_2, y_2)$，那么 $y_2 = x_1 < x_2$，和这一段里 $x_2 \le y_2$ 矛盾。用 C 写没有集合时，就在 x = 0 和 x = y 时各只画 4 个点，r = 0 单独处理。 ## 复杂度 -- 时间 O(r)。八分之一段大约有 r/√2 列，每列 O(1)。像素总数约 8 × r/√2 = 4√2 r ≈ 5.66r，每个像素 `plot` 一次。 -- 额外空间 O(1)：像素直接交给 `plot`，不存下来。 +- 时间 $O(r)$。八分之一段大约有 $r/\sqrt{2}$ 列，每列 $O(1)$。像素总数约 $8 \times r/\sqrt{2} = 4\sqrt{2}\,r \approx 5.66r$，每个像素 `plot` 一次。 +- 额外空间 $O(1)$：像素直接交给 `plot`，不存下来。 - 每列的乘法和开方次数见思路第 6 节的表：第五版两样都没有。 @@ -259,8 +267,8 @@ - **只画严格在圆上的整点**（思路第 1 节）：r = 3 只剩四个点。 -- **x 从 0 到 r 逐列取整**（第 2 节）：靠近 (±r, 0) 的陡弧会断开。 -- **8 个对称点抄错**（第 3 节）：二手资料把 (y, x) 写了两遍、漏了 (y, −x)，右边从 (r, 0) 往下到对角线 y = −x 那一段弧就空了，r = 3 时少 (3, −1)。 -- **循环条件写成 `x < y`**（第 3 节）：漏掉 x 恰好等于 y 的那一列，r = 3 时少 (±2, ±2)。 -- **中点判断方向弄反**（第 4 节）：中点在圆内（f < 0，代码里是 d < 0）选上面的 y，不是 y − 1。 +- **x 从 0 到 r 逐列取整**（第 2 节）：靠近 $(\pm r, 0)$ 的陡弧会断开。 +- **8 个对称点抄错**（第 3 节）：二手资料把 $(y, x)$ 写了两遍、漏了 $(y, -x)$，右边从 (r, 0) 往下到对角线 $y = -x$ 那一段弧就空了，r = 3 时少 $(3, -1)$。 +- **循环条件写成 `x < y`**（第 3 节）：漏掉 x 恰好等于 y 的那一列，r = 3 时少 $(\pm 2, \pm 2)$。 +- **中点判断方向弄反**（第 4 节）：中点在圆内（$f < 0$，代码里是 $d < 0$）选上面的 y，不是 $y - 1$。 - **先改 x、y 再加增量**（第 5 节）：两个增量公式里的 x、y 是更新之前的值。 - **r 不是整数还用整数 d**（第 5 节末）：r = 1.1 时会多画 (1, 1)，要改用 P 本身。 @@ -275,15 +283,15 @@ - **第二版会断**：r 从 2 到 2000，第二版画出的圆全部不是 8 连通的。r = 5 的断口和思路第 2 节的图一致。 - **第三版、第四版、`draw_circle` 完全一致**：r 从 0 到 2000，三者的像素集合逐一相同。 -- **每一列都是最近的整数**：r 从 1 到 2000，八分之一段每一列的 y 都满足 (2y − 1)² < 4(r² − x²) < (2y + 1)²，即 y 是离 Y(x) 最近的整数。这一项只用整数运算核对，不经过浮点。相邻两列 y 的降幅最大是 1。 +- **每一列都是最近的整数**：r 从 1 到 2000，八分之一段每一列的 y 都满足 $(2y - 1)^2 < 4(r^2 - x^2) < (2y + 1)^2$，即 y 是离 $Y(x)$ 最近的整数。这一项只用整数运算核对，不经过浮点。相邻两列 y 的降幅最大是 1。 - **整圈不断**：r 从 1 到 2000，`draw_circle` 画出的像素用广度优先搜索（BFS）检查，全部 8 连通。 -- **r = 5 的递推表**：`draw_circle` 每一步的 (x, y, d) 和思路第 5 节的表一致，而且每一步 d 都等于用分数（`fractions.Fraction`）精确算出的 f(x + 1, y − ½) − ¼。 +- **r = 5 的递推表**：`draw_circle` 每一步的 (x, y, d) 和思路第 5 节的表一致，而且每一步 d 都等于用分数（`fractions.Fraction`）精确算出的 $f(x + 1, y - \tfrac{1}{2}) - \tfrac{1}{4}$。 - **r = 10 的两段弧**：平弧 x 从 0 到 7 共 8 列。陡弧 x 从 7 到 10 共 4 列，y 是 7、6、4、0。 -- **`x < y` 的写法**：把 `draw_circle` 的 `while x <= y` 改成 `while x < y`，r = 3 时只画出 12 个点，少的正是 (±2, ±2)。 -- **不重复、可平移**：r 从 0 到 300，`draw_circle` 对每个像素只调用一次 `plot`。r = 0 只画 (0, 0)。圆心 (10, −4) 时结果是圆心 (0, 0) 的整体平移。r = −1 抛出 `ValueError`。对 0 < x < y 的点，`mirror8` 返回 8 个不同的点。 +- **`x < y` 的写法**：把 `draw_circle` 的 `while x <= y` 改成 `while x < y`，r = 3 时只画出 12 个点，少的正是 $(\pm 2, \pm 2)$。 +- **不重复、可平移**：r 从 0 到 300，`draw_circle` 对每个像素只调用一次 `plot`。r = 0 只画 (0, 0)。圆心 $(10, -4)$ 时结果是圆心 (0, 0) 的整体平移。$r = -1$ 抛出 `ValueError`。对 $0 < x < y$ 的点，`mirror8` 返回 8 个不同的点。 - **像素个数**：r = 1、2、3、5、10、100、1000 时分别是 4、12、16、28、56、564、5656 个。 -- **涂满（Follow-up 2）**：r 从 0 到 200，`fill_circle` 对每个像素只调用一次 `plot`，每一行涂的范围恰好从这一行最左边的圆周像素到最右边的圆周像素，`draw_circle` 的每个像素都被涂到。r = −1 抛出 `ValueError`。r = 3 时涂了 37 个像素，x² + y² ≤ 9 的整点只有 29 个。r = 100 时涂了 31689 个，π·100² ≈ 31416。 -- **d 的大小（Follow-up 3）**：r 从 1 到 2000，用来做判断的每个 d 都满足 |d| ≤ 2r + 1，|d| / r 最大是 1.95（r = 1936）。循环结束时的 |d| / r 最大是 3（r = 1 时 d = 3），都在 4r + 4 以内。r² 在 r = 46341 时第一次超过 2³¹ − 1，4r² 在 r = 23171 时第一次超过。 -- **r 不是整数（思路第 5 节末）**：这一项是另写的一段检查，页面上没有对应的代码块，全程用分数（`fractions.Fraction`）精确计算。r 取 0.1 到 399.9 之间步长 0.1 的 3600 个非整数，判断某个 y 是否最近时允许并列。照搬整数 d 的写法，有 505 个 r 画出了不是最近的像素，第一个是 r = 1.1（八分之一段画出 (0, 1)、(1, 1)）。直接维护 P 的写法全部正确，相邻两列 y 只差 0 或 1。r = 2.5 时走到 (1, 2) 那一步 P = 0。r 取 0.5 到 399.5 的 400 个「整数 + ½」时，起点取较小或较大的整数，两种都全部正确。 -- **二手资料的对称列表**（和上一项同一段另写的检查）：把 (y, −x) 换成重复的 (y, x)，r = 3 时少 (3, −1)，r = 5 时少 (5, −1)、(5, −2)、(4, −3)，都在右边 x 轴下方。 +- **涂满（Follow-up 2）**：r 从 0 到 200，`fill_circle` 对每个像素只调用一次 `plot`，每一行涂的范围恰好从这一行最左边的圆周像素到最右边的圆周像素，`draw_circle` 的每个像素都被涂到。$r = -1$ 抛出 `ValueError`。r = 3 时涂了 37 个像素，$x^2 + y^2 \le 9$ 的整点只有 29 个。r = 100 时涂了 31689 个，$\pi \cdot 100^2 \approx 31416$。 +- **d 的大小（Follow-up 3）**：r 从 1 到 2000，用来做判断的每个 d 都满足 $|d| \le 2r + 1$，$|d| / r$ 最大是 1.95（r = 1936）。循环结束时的 $|d| / r$ 最大是 3（r = 1 时 d = 3），都在 $4r + 4$ 以内。$r^2$ 在 r = 46341 时第一次超过 $2^{31} - 1$，$4r^2$ 在 r = 23171 时第一次超过。 +- **r 不是整数（思路第 5 节末）**：这一项是另写的一段检查，页面上没有对应的代码块，全程用分数（`fractions.Fraction`）精确计算。r 取 0.1 到 399.9 之间步长 0.1 的 3600 个非整数，判断某个 y 是否最近时允许并列。照搬整数 d 的写法，有 505 个 r 画出了不是最近的像素，第一个是 r = 1.1（八分之一段画出 (0, 1)、(1, 1)）。直接维护 P 的写法全部正确，相邻两列 y 只差 0 或 1。r = 2.5 时走到 (1, 2) 那一步 P = 0。r 取 0.5 到 399.5 的 400 个「整数 + $\tfrac{1}{2}$」时，起点取较小或较大的整数，两种都全部正确。 +- **二手资料的对称列表**（和上一项同一段另写的检查）：把 $(y, -x)$ 换成重复的 $(y, x)$，r = 3 时少 $(3, -1)$，r = 5 时少 $(5, -1)$、$(5, -2)$、$(4, -3)$，都在右边 x 轴下方。 ## Follow-up @@ -321,16 +329,16 @@ ``` -这样涂是对的，因为圆周像素 (x, y) 和它镜像出来的 (y, x)，分别落在第 y 行和第 x 行，所以每一行的最右端都记下来了。每一行都会被记到。用思路第 3 节的记号，八分之一段最后一个像素是 (x_end, y_end)：y 从 r 往下每次最多减 1，覆盖了第 y_end 到第 r 行。x 从 0 往上覆盖了第 0 到第 x_end 行。第 3 节证过 y_end − x_end ≤ 1，所以两段之间不会漏行。左右、上下对称，所以第 k 行从 −half[k] 涂到 half[k]。每个像素只 `plot` 一次。 - -不直接涂 x² + y² ≤ r² 的点，是因为那样涂出来的边和圆周像素对不上：r = 3 时 (1, 3) 是圆周像素，但 1 + 9 > 9，它不在 x² + y² ≤ 9 里面。涂满的区域里应该包含画出来的那圈边。 - -代价是时间 O(r²)，因为要涂的像素本来就有约 πr² 个，省不掉。额外空间 O(r)，存每行的半宽。实测见测试用例。 +这样涂是对的，因为圆周像素 (x, y) 和它镜像出来的 (y, x)，分别落在第 y 行和第 x 行，所以每一行的最右端都记下来了。每一行都会被记到。用思路第 3 节的记号，八分之一段最后一个像素是 $(x_{\text{end}}, y_{\text{end}})$：y 从 r 往下每次最多减 1，覆盖了第 $y_{\text{end}}$ 到第 r 行。x 从 0 往上覆盖了第 0 到第 $x_{\text{end}}$ 行。第 3 节证过 $y_{\text{end}} - x_{\text{end}} \le 1$，所以两段之间不会漏行。左右、上下对称，所以第 k 行从 $-\mathrm{half}[k]$ 涂到 $\mathrm{half}[k]$。每个像素只 `plot` 一次。 + +不直接涂 $x^2 + y^2 \le r^2$ 的点，是因为那样涂出来的边和圆周像素对不上：r = 3 时 (1, 3) 是圆周像素，但 $1 + 9 > 9$，它不在 $x^2 + y^2 \le 9$ 里面。涂满的区域里应该包含画出来的那圈边。 + +代价是时间 $O(r^2)$，因为要涂的像素本来就有约 $\pi r^2$ 个，省不掉。额外空间 $O(r)$，存每行的半宽。实测见测试用例。 ### 3. 用 C 写，32 位整数会不会溢出 -192327 的发帖人说做存储的公司很看重 C/C++，所以这一问值得准备。32 位有符号整数最大是 2³¹ − 1 = 2147483647。 - -- 第一到第三版要算 r·r，r = 46341 时 r² = 2147488281，已经溢出。第四版要算 4r²，r = 23171 时就溢出。 -- 第五版只存 d、x、y，不算 r²。d 有多大可以这样估计。先把当前像素 (x, y) 代入圆方程，e = x² + y² − r² = (y − Y(x)) · (y + Y(x))：y 是离 Y(x) 最近的整数，第一个因子的绝对值小于 ½。y 和 Y(x) 都不超过 r，第二个因子不超过 2r，所以 |e| < r。判断用的 P = f(x + 1, y − ½) 展开是 e + (2x − y) + 5/4，而 0 ≤ x ≤ y ≤ r，所以 |2x − y| ≤ r。合起来 |P| < 2r + 5/4，d = P − ¼ 是整数，所以 |d| ≤ 2r + 1。循环最后那次更新以后 d 不再使用，它只多加了一个绝对值不超过 2r + 3 的增量，所以 d 存过的所有值都在 4r + 4 以内。r 不超过 5 亿时，4r + 4 ≈ 20 亿，32 位整数装得下。实测见测试用例。 +192327 的发帖人说做存储的公司很看重 C/C++，所以这一问值得准备。32 位有符号整数最大是 $2^{31} - 1 = 2147483647$。 + +- 第一到第三版要算 $r \cdot r$，r = 46341 时 $r^2 = 2147488281$，已经溢出。第四版要算 $4r^2$，r = 23171 时就溢出。 +- 第五版只存 d、x、y，不算 $r^2$。d 有多大可以这样估计。先把当前像素 $(x, y)$ 代入圆方程，$e = x^2 + y^2 - r^2 = (y - Y(x)) \cdot (y + Y(x))$：y 是离 $Y(x)$ 最近的整数，第一个因子的绝对值小于 $\tfrac{1}{2}$。y 和 $Y(x)$ 都不超过 r，第二个因子不超过 2r，所以 $|e| < r$。判断用的 $P = f(x + 1, y - \tfrac{1}{2})$ 展开是 $e + (2x - y) + \tfrac{5}{4}$，而 $0 \le x \le y \le r$，所以 $|2x - y| \le r$。合起来 $|P| < 2r + \tfrac{5}{4}$，$d = P - \tfrac{1}{4}$ 是整数，所以 $|d| \le 2r + 1$。循环最后那次更新以后 d 不再使用，它只多加了一个绝对值不超过 $2r + 3$ 的增量，所以 d 存过的所有值都在 $4r + 4$ 以内。r 不超过 5 亿时，$4r + 4 \approx$ 20 亿，32 位整数装得下。实测见测试用例。 ## 英文讲法
meta
@@ -1,5 +1,5 @@ { "depth_guide": "2026-10-23", - "rewritten_by": "local", - "rewritten_at": "2026-10-25" + "rewritten_by": "cloud:20261026-2311", + "rewritten_at": "2026-10-27" }