题目描述

给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint。

说明

• 输入值和输出值都将是 浮点数 。
• 圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。
• 圆周上的点也认为是在圆中。
• randPoint 返回一个包含随机点的 x 坐标和 y 坐标的大小为 2 的数组。

样例

输入: 
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

输入: 
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

输入语法说明

• 输入是两个列表：调用成员函数名和调用的参数。
• Solution 的构造函数有三个参数，圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

算法

(矩形内采样) $O(1)$

1. 在圆外切矩形内撒点采样。
2. 如果采样的点在圆内，返回；否则重新采样。
3. 由于二维的每一维都是均匀分布的，所以结果也是均匀分布的。

时间复杂度

• 平均每轮需要 $\frac{4}{\pi} = 1.273$ 次采样。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    double r, x, y;

public:
    Solution(double radius, double x_center, double y_center) {
        r = radius;
        x = x_center;
        y = y_center;
    }

    vector<double> randPoint() {
        while (1) {
            double cx = 2 * r * rand() / RAND_MAX - r + x;
            double cy = 2 * r * rand() / RAND_MAX - r + y;
            if ((cx - x) * (cx - x) + (cy - y) * (cy - y) <= r * r)
                return {cx, cy};
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */

算法2

(直接采样) $O(1)$

1. 考虑直接在圆内撒点采样。
2. 圆内的点有两个参数，距离圆心的距离和角度。
3. 距离圆心的距离是二维的，需要在 [0, r^2] 内采样然后开方，才能保证是均匀分布。
4. 角度直接在 [0, 2 * pi] 内采样就可以。
5. 最后计算在当前距离和角度下的二维坐标。

时间复杂度

• 每一轮仅需要随机一次。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    double r, x, y;

public:
    Solution(double radius, double x_center, double y_center) {
        r = radius;
        x = x_center;
        y = y_center;
    }

    vector<double> randPoint() {
        double cr = r * sqrt(1.0 * rand() / RAND_MAX);
        double angle = 2 * M_PI * rand() / RAND_MAX;
        double cx = x + cr * cos(angle), cy = y + cr * sin(angle);
        return {cx, cy};
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */