478. Generate Random Point in a Circle - cocoder39/coco39_LC GitHub Wiki

478. Generate Random Point in a Circle

rejection sampling

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.x_begin = x_center - radius
        self.x_end = x_center + radius
        self.y_begin = y_center - radius
        self.y_end = y_center + radius
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

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

area of square is (2R)^2 = 4(R^2). Area of circle is 3.14(R^2). So P(a point falls into circle) = 3.14/4. We need to sample 1/(3.14/4) = 1.274 times to generate a valid point. Time complexity is O(1) on average but O(∞) worst case.

space complexity is O(1)