题目

给定圆的半径和圆心的位置，实现函数 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 次

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

思路

在圆外套一个正方形，随机生成[x-r,x+r]的x和[y-r,y+r]的y，如果该点在圆内就返回，不在就继续随机采样。期望的时间复杂度为O(1)。

代码

  1. class Solution {
  2.     double x;
  3.     double y;
  4.     double r;
  6.     public Solution(double radius, double x_center, double y_center) {
  7.         r = radius;
  8.         x = x_center;
  9.         y = y_center;
  10.     }
  12.     public double[] randPoint() {
  13.         while (true) {
  14.             double x1 = Math.random() * 2 * r + x - r;
  15.             double y1 = Math.random() * 2 * r + y - r;
  16.             if ((x - x1) * (x - x1) + (y - y1) * (y - y1) <= r * r) {
  17.                 return new double[]{x1, y1};
  18.             }
  19.         }
  20.     }
  21. }
  23. /**
  24.  * Your Solution object will be instantiated and called as such:
  25.  * Solution obj = new Solution(radius, x_center, y_center);
  26.  * double[] param_1 = obj.randPoint();
  27.  */