478. 在圆内随机生成点

给定圆的半径和圆心的位置，实现函数 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 <= 108
• -107 <= x_center, y_center <= 107
• randPoint 最多被调用 3 * 104 次

思路

利用勾股定理 x * x + y + y <= radius * redius。

方法一：拒绝采样

image.png

class Solution {
    Random random = new Random();
    double radius;
    double x_center ;
    double y_center ;
    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center ;
        this.y_center = y_center ;
    }
    
    public double[] randPoint() {
        while(true){
            double randomX = random.nextDouble() * (radius * 2) - radius ;
            double randomY = random.nextDouble() * (radius * 2) - radius;
            if (randomX * randomX + randomY * randomY <= radius * radius)
                return new double[]{randomX + x_center , randomY + y_center};
        }
    }
}

参考答案：自己写的

class Solution {

    double radius;
    double x_center;
    double y_center;

    Random random = new Random();

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
    }
    
    public double[] randPoint() {
        double x = random.nextDouble() * radius;
        double y = random.nextDouble() * radius;
        Double r = radius * radius;
        // double 类型比较大小使用 compareTo。本题，直接比较也是可以通过的
       while (r.compareTo(x * x + y * y) < 0) {
            x = random.nextDouble() * radius;
            y = random.nextDouble() * radius;
        }
        // 总共 4 个象限
        int i = random.nextInt(4) + 1;
        switch (i) {
            case 1:
                x = -x;
                break;
            case 2:
                break;
            case 3:
                x = -x;
                y = -y;
                break;
            case 4:
                y = -y;
                break;
            default:
        }
        x += x_center;
        y += y_center;
        return new double[]{x, y};
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(radius, x_center, y_center);
 * double[] param_1 = obj.randPoint();
 */

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/generate-random-point-in-a-circle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。