0478. 在圆内随机生成点【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 拒绝采样

1. 📝 题目描述

• leetcode

给定圆的半径和圆心的位置，实现函数 randPoint，在圆中产生均匀随机点。

实现 Solution 类:

• Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
• randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y]。

---

示例 1：

输入:
["Solution","randPoint","randPoint","randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
输出: [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]
解释:
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint ();//返回[-0.02493，-0.38077]
solution.randPoint ();//返回[0.82314,0.38945]
solution.randPoint ();//返回[0.36572,0.17248]

---

提示：

• 0 < radius <= 10^8
• -10^7 <= x_center, y_center <= 10^7
• randPoint 最多被调用 3 * 10^4 次

2. 🎯 s.1 - 拒绝采样

c

typedef struct {
    double r, x, y;
} Solution;

Solution* solutionCreate(double radius, double x_center, double y_center) {
    Solution* obj = (Solution*)malloc(sizeof(Solution));
    obj->r = radius; obj->x = x_center; obj->y = y_center;
    return obj;
}

double* solutionRandPoint(Solution* obj, int* retSize) {
    *retSize = 2;
    double* res = (double*)malloc(sizeof(double) * 2);
    while (1) {
        double x = (double)rand() / RAND_MAX * 2 * obj->r - obj->r;
        double y = (double)rand() / RAND_MAX * 2 * obj->r - obj->r;
        if (x * x + y * y <= obj->r * obj->r) {
            res[0] = obj->x + x;
            res[1] = obj->y + y;
            return res;
        }
    }
}

void solutionFree(Solution* obj) { free(obj); }

js

/**
 * @param {number} radius
 * @param {number} x_center
 * @param {number} y_center
 */
var Solution = function (radius, x_center, y_center) {
  this.r = radius
  this.x = x_center
  this.y = y_center
}

/**
 * @return {number[]}
 */
Solution.prototype.randPoint = function () {
  while (true) {
    const x = Math.random() * 2 * this.r - this.r
    const y = Math.random() * 2 * this.r - this.r
    if (x * x + y * y <= this.r * this.r) return [this.x + x, this.y + y]
  }
}

py

class Solution:
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.r = radius
        self.x = x_center
        self.y = y_center

    def randPoint(self) -> List[float]:
        while True:
            x = random.uniform(-self.r, self.r)
            y = random.uniform(-self.r, self.r)
            if x * x + y * y <= self.r * self.r:
                return [self.x + x, self.y + y]

• 时间复杂度：期望 $O(1)$（采样成功概率 $\pi /4\approx 0.785$）
• 空间复杂度：$O(1)$

算法思路：

• 在外接正方形内均匀随机生成点
• 若点在圆内则接受，否则重新采样