Problem

Given the radius and the position of the center of a circle, implement the function randPoint which generates a uniform random point inside the circle.

Implement the Solution class:

  • Solution(double radius, double x_center, double y_center) initializes the object with the radius of the circle radius and the position of the center (x_center, y_center).
  • randPoint() returns a random point inside the circle. A point on the circumference of the circle is considered to be in the circle. The answer is returned as an array [x, y].

Examples

Example 1:

1
2
3
4
5

**Input**
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
**Output**
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation

1
2
3
4

Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

Solution

Method 1 – Polar Coordinates Sampling

Intuition

To generate a uniform random point inside a circle, we use polar coordinates. The angle is chosen uniformly from [0, 2π), and the radius is chosen so that points are uniformly distributed (using sqrt of a uniform random variable).

Approach

  1. For each random point, generate a random angle θ in [0, 2π).
  2. Generate a random radius r in [0, radius], but use r = radius * sqrt(U) where U is uniform in [0,1] to ensure uniform distribution.
  3. Convert polar coordinates (r, θ) to Cartesian: x = x_center + rcos(θ), y = y_center + rsin(θ).
  4. Return [x, y].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    double rad, xc, yc;
public:
    Solution(double radius, double x_center, double y_center) : rad(radius), xc(x_center), yc(y_center) {}
    vector<double> randPoint() {
        double theta = 2 * M_PI * ((double)rand() / RAND_MAX);
        double r = rad * sqrt((double)rand() / RAND_MAX);
        return {xc + r * cos(theta), yc + r * sin(theta)};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import (
    "math"
    "math/rand"
)
type Solution struct {
    rad, xc, yc float64
}
func Constructor(radius, x_center, y_center float64) Solution {
    return Solution{radius, x_center, y_center}
}
func (s *Solution) RandPoint() []float64 {
    theta := 2 * math.Pi * rand.Float64()
    r := s.rad * math.Sqrt(rand.Float64())
    return []float64{s.xc + r*math.Cos(theta), s.yc + r*math.Sin(theta)}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    double rad, xc, yc;
    public Solution(double radius, double x_center, double y_center) {
        rad = radius; xc = x_center; yc = y_center;
    }
    public double[] randPoint() {
        double theta = 2 * Math.PI * Math.random();
        double r = rad * Math.sqrt(Math.random());
        return new double[]{xc + r * Math.cos(theta), yc + r * Math.sin(theta)};
    }
}
1
2
3
4
5
6
7

class Solution(val rad: Double, val xc: Double, val yc: Double) {
    fun randPoint(): DoubleArray {
        val theta = 2 * Math.PI * Math.random()
        val r = rad * Math.sqrt(Math.random())
        return doubleArrayOf(xc + r * Math.cos(theta), yc + r * Math.sin(theta))
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import random, math
class Solution:
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.rad = radius
        self.xc = x_center
        self.yc = y_center
    def randPoint(self) -> list[float]:
        theta = 2 * math.pi * random.random()
        r = self.rad * math.sqrt(random.random())
        return [self.xc + r * math.cos(theta), self.yc + r * math.sin(theta)]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

use rand::Rng;
impl Solution {
    fn new(radius: f64, x_center: f64, y_center: f64) -> Self {
        Solution { rad: radius, xc: x_center, yc: y_center }
    }
    fn rand_point(&self) -> Vec<f64> {
        let mut rng = rand::thread_rng();
        let theta = 2.0 * std::f64::consts::PI * rng.gen::<f64>();
        let r = self.rad * rng.gen::<f64>().sqrt();
        vec![self.xc + r * theta.cos(), self.yc + r * theta.sin()]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    rad: number; xc: number; yc: number;
    constructor(radius: number, x_center: number, y_center: number) {
        this.rad = radius; this.xc = x_center; this.yc = y_center;
    }
    randPoint(): number[] {
        const theta = 2 * Math.PI * Math.random();
        const r = this.rad * Math.sqrt(Math.random());
        return [this.xc + r * Math.cos(theta), this.yc + r * Math.sin(theta)];
    }
}

Complexity

  • ⏰ Time complexity: O(1), each call generates a point in constant time.
  • 🧺 Space complexity: O(1), only a constant amount of extra space is used.

Method 2 -

Code

Complexity

  • Time: O(nnnxxxnnn)
  • Space: O(nnnxxx)