# LeetCode 478: Generate Random Point in a Circle

## Problem Restatement

We are given a circle defined by:

| Value | Meaning |
|---|---|
| `radius` | Radius of the circle |
| `x_center` | x-coordinate of the center |
| `y_center` | y-coordinate of the center |

We need to implement a class with two parts:

| Method | Meaning |
|---|---|
| `Solution(radius, x_center, y_center)` | Stores the circle |
| `randPoint()` | Returns a random point inside or on the circle |

The returned point must be uniformly distributed inside the circle. A point on the circumference is allowed. The answer is returned as `[x, y]`.

## Input and Output

| Item | Meaning |
|---|---|
| Constructor input | `radius`, `x_center`, `y_center` |
| Method output | A random point `[x, y]` |
| Point type | Floating-point coordinates |
| Valid point | Any point inside or on the circle |
| Required distribution | Uniform over the circle area |

Class shape:

```python
class Solution:

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

    def randPoint(self) -> list[float]:
        ...
```

## Examples

Example 1:

```python
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
```

The circle has radius `1` and center `(0, 0)`.

Each call to `randPoint()` returns a random point inside the unit circle.

Possible output:

```python
[None, [-0.72, -0.65], [-0.78, -0.28], [-0.83, -0.19]]
```

The exact values are random, so many different outputs are valid.

Example 2:

```python
["Solution", "randPoint", "randPoint", "randPoint"]
[[10.0, 5.0, -7.5], [], [], []]
```

The circle has radius `10` and center `(5, -7.5)`.

Each returned point must lie inside that circle.

## First Thought: Pick Random x and y

A simple idea is to pick:

```python
x = random.uniform(x_center - radius, x_center + radius)
y = random.uniform(y_center - radius, y_center + radius)
```

This picks a point inside the square that surrounds the circle.

But the square contains points outside the circle.

For example, with center `(0, 0)` and radius `1`, the point `(1, 1)` is inside the square, but outside the circle because:

```text
1^2 + 1^2 = 2 > 1^2
```

So we must either reject points outside the circle, or generate points directly inside the circle.

## Brute Force With Rejection Sampling

The rejection sampling method is simple:

1. Pick a random point inside the bounding square.
2. Check whether it lies inside the circle.
3. If yes, return it.
4. If no, try again.

Code:

```python
import random

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.x_center - self.radius, self.x_center + self.radius)
            y = random.uniform(self.y_center - self.radius, self.y_center + self.radius)

            dx = x - self.x_center
            dy = y - self.y_center

            if dx * dx + dy * dy <= self.radius * self.radius:
                return [x, y]
```

This is correct and often accepted.

The square area is:

```text
(2r) * (2r) = 4r^2
```

The circle area is:

```text
pi * r^2
```

So the probability that a random square point lands inside the circle is:

```text
(pi * r^2) / (4r^2) = pi / 4
```

That is about `0.785`.

So the expected number of attempts is about:

```text
4 / pi ≈ 1.27
```

This is efficient in practice.

## Key Insight

We can also generate the point directly using polar coordinates.

A point inside a circle can be described by:

| Value | Meaning |
|---|---|
| `r` | Distance from the center |
| `theta` | Angle from the positive x-axis |

Then the point is:

```python
x = x_center + r * cos(theta)
y = y_center + r * sin(theta)
```

The angle should be uniform from `0` to `2π`.

The radius needs care.

We cannot choose `r` uniformly from `0` to `radius`.

That would put too many points near the center. The outer rings have more area than the inner rings, so they should receive more points.

Area grows with the square of the radius:

```text
area = pi * r^2
```

To make area uniform, choose a random value `u` from `0` to `1`, then use:

```python
r = radius * sqrt(u)
```

This makes the probability proportional to area, not raw distance.

## Algorithm

Store the circle values in the constructor.

For each call to `randPoint()`:

1. Generate a random number `u` in `[0, 1)`.
2. Set `r = radius * sqrt(u)`.
3. Generate a random angle `theta` in `[0, 2π)`.
4. Convert from polar coordinates to Cartesian coordinates.
5. Shift the point by the circle center.
6. Return `[x, y]`.

## Correctness

The angle `theta` is chosen uniformly from `0` to `2π`, so every direction from the center has equal probability.

The distance `r` is chosen as:

```python
radius * sqrt(u)
```

where `u` is uniform in `[0, 1)`.

For any distance `a` between `0` and `radius`, the probability that the generated point lies within distance `a` of the center is:

```text
P(r <= a)
= P(radius * sqrt(u) <= a)
= P(u <= a^2 / radius^2)
= a^2 / radius^2
```

That matches the area ratio between the smaller circle of radius `a` and the full circle:

```text
(pi * a^2) / (pi * radius^2)
= a^2 / radius^2
```

Therefore, the generated point is uniform by area.

The Cartesian conversion:

```python
x = x_center + r * cos(theta)
y = y_center + r * sin(theta)
```

places the point exactly at distance `r` from the center in direction `theta`.

Since `r <= radius`, every returned point is inside or on the circle.

Thus the algorithm returns uniformly random valid points inside the circle.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Constructor time | `O(1)` | Stores three values |
| `randPoint` time | `O(1)` | Uses a fixed number of random and math operations |
| Space | `O(1)` | Stores only circle parameters |

## Implementation

```python
import math
import random

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]:
        u = random.random()
        r = self.radius * math.sqrt(u)

        theta = random.random() * 2 * math.pi

        x = self.x_center + r * math.cos(theta)
        y = self.y_center + r * math.sin(theta)

        return [x, y]
```

## Code Explanation

The constructor stores the circle:

```python
self.radius = radius
self.x_center = x_center
self.y_center = y_center
```

This line chooses a random area fraction:

```python
u = random.random()
```

Then we convert that area fraction into a radius:

```python
r = self.radius * math.sqrt(u)
```

The square root is the important part. Without it, the distribution would cluster near the center.

This line chooses a random direction:

```python
theta = random.random() * 2 * math.pi
```

Then we convert from polar coordinates to x and y:

```python
x = self.x_center + r * math.cos(theta)
y = self.y_center + r * math.sin(theta)
```

Finally, return the point:

```python
return [x, y]
```

## Testing

Randomized problems cannot be tested with exact expected output.

Instead, we test properties that every output must satisfy.

```python
def run_tests():
    s = Solution(1.0, 0.0, 0.0)

    for _ in range(10000):
        x, y = s.randPoint()
        assert x * x + y * y <= 1.0 + 1e-12

    s = Solution(10.0, 5.0, -7.5)

    for _ in range(10000):
        x, y = s.randPoint()
        dx = x - 5.0
        dy = y + 7.5
        assert dx * dx + dy * dy <= 100.0 + 1e-12

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Unit circle centered at `(0, 0)` | Checks basic circle geometry |
| Larger shifted circle | Checks center offset logic |
| Many generated points | Checks repeated random calls |
| Small tolerance `1e-12` | Allows tiny floating-point error |