Generate Random Point in a Circle

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].

For example:

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

Constraints:

• 0 < radius <= 10^8
• -10^7 <= x_center, y_center <= 10^7
• At most 3 * 10^4 calls will be made to randPoint.

import random
import math

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self) -> list[float]:
        while True:
            x = random.uniform(-self.radius, self.radius)
            y = random.uniform(-self.radius, self.radius)
            if x**2 + y**2 <= self.radius**2:
                return [self.x_center + x, self.y_center + y]


# Your Solution object will be instantiated and called as such:
# obj = Solution(radius, x_center, y_center)
# param_1 = obj.randPoint()

Explanation:

1. Initialization: The constructor stores the radius and the center coordinates of the circle.
2. randPoint() method:
   • It generates random x and y coordinates within a square that encloses the circle. This is done using random.uniform(-self.radius, self.radius) to generate random floats between -radius and radius.
   • It checks if the generated point (x, y) lies inside the circle using the equation x**2 + y**2 <= self.radius**2. This equation is based on the distance formula from the center (0,0) since we are generating coordinates relative to the center.
   • If the point is inside the circle, it shifts the coordinates to the actual center (x_center, y_center) and returns the point [self.x_center + x, self.y_center + y].
   • If the point is outside the circle, it repeats the process until a point inside the circle is found. This is achieved with a while True loop.

Example Usage:

# Example Usage:
radius = 1.0
x_center = 0.0
y_center = 0.0

solution = Solution(radius, x_center, y_center)

point1 = solution.randPoint()
print(point1)

point2 = solution.randPoint()
print(point2)

point3 = solution.randPoint()
print(point3)

Big O Runtime Analysis

• __init__: O(1). The constructor simply stores the radius and center coordinates, which takes constant time.
• randPoint: O(1) on average, but could be O(infinity) in the worst case. While the while loop appears to potentially run forever, in practice, it converges to O(1) because the probability of finding a point inside the circle within a reasonable number of attempts is very high. The ratio of the circle's area to the square's area is pi/4 which is roughly 0.785. This means approximately 78.5% of the randomly generated points will fall inside the circle. Therefore, the expected number of iterations is a small constant.

Big O Space Usage Analysis

• __init__: O(1). The constructor stores a fixed number of variables (radius, x_center, y_center).
• randPoint: O(1). The function uses a fixed number of variables to generate and store the random point.