0478. Generate Random Point in a Circle

题目信息

题号:

0478

难度:

Medium

主题:

圆形区域、二维随机点、均匀面积分布、对象状态

原题:

LeetCode 0478

重点:

返回点必须位于圆内或圆周、圆内等面积区域概率相同、构造参数在多次调用间保持

题目重述

实现 Solution 类。构造函数接收圆的半径 radius 和圆心坐标 x_center、y_center;randPoint() 每次返回圆内或圆周上的一个随机点 [x, y]。

随机分布必须在圆的面积上均匀:任意两个面积相等的子区域被选中的概率相同,不能让靠近圆心或圆周的区域获得额外概率。返回点必须满足:

(x - x_center)^2 + (y - y_center)^2 <= radius^2

radius 位于 (0, 10^8],圆心坐标位于 [-10^7, 10^7],调用次数不超过 3 * 10^4。具体单次输出不可预先确定。

自建示例

检查输出范围:

构造:Solution(3, 2, -1)
调用:randPoint()
输出:例如 [3.2, 0.5],也可能是圆内其他点
解释:(3.2-2)^2 + (0.5+1)^2 = 3.69 <= 9,因此示例点位于圆内;每次调用可以返回不同结果。

均匀性要求:

调用:大量重复执行 randPoint()
输出:所有点都在圆内
解释:长期统计应按面积均匀分布,不能简单让半径在 0..radius 上均匀而导致圆心附近过密。

在外接正方形中拒绝采样

先在 [-1,1] × [-1,1] 正方形中均匀生成偏移量 (dx,dy),若 dx^2 + dy^2 > 1 就丢弃并重试,否则把偏移量乘以半径再平移到圆心。正方形中被接受的点仍然保持均匀,而接受区域正是单位圆,因此得到按面积均匀的圆内点。

不能把半径直接均匀取在 [0,radius] 上,因为半径越小的同心圆环面积越小,会造成圆心附近过密;拒绝采样避免了这个偏差。

C++ 实现

class Solution {
    double radius;
    double centerX;
    double centerY;

    double uniform(double left, double right) {
        return left + (right - left) *
                         (std::rand() / static_cast<double>(RAND_MAX));
    }

public:
    Solution(double radius, double x_center, double y_center)
        : radius(radius), centerX(x_center), centerY(y_center) {}

    std::vector<double> randPoint() {
        double dx = 0;
        double dy = 0;
        do {
            dx = uniform(-1.0, 1.0);
            dy = uniform(-1.0, 1.0);
        } while (dx * dx + dy * dy > 1.0);

        return {centerX + radius * dx, centerY + radius * dy};
    }
};

代码分析

被接受的偏移点在单位圆内均匀分布,缩放和平移只改变坐标,不改变相对面积概率;边界是否恰好命中圆周不影响连续分布。每次尝试使用常数空间,接受概率为 pi/4,因此期望尝试次数为常数,额外空间复杂度为 O(1)。