Leetcode 478: Generate Random Point in a Circle

https://leetcode.com/problems/generate-random-point-in-a-circle/description/

Given the radius and x-y positions of the center of a circle, write a function randPoint which generates a uniform random point in the circle.

Note:

1. input and output values are in floating-point.
2. radius and x-y position of the center of the circle is passed into the class constructor.
3. a point on the circumference of the circle is considered to be in the circle.
4. randPoint returns a size 2 array containing x-position and y-position of the random point, in that order.

Example 1:

Input: 
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
Output: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

Example 2:

Input: 
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
Output: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint has no arguments. Arguments are always wrapped with a list, even if there aren't any.

Notes:

A very classic interview question.

The key is how to achieve a real random distribution in a circle?

There are some math or probability involved. But it should be intuitive that the probability to find a point inside a circle should be proportional to the area of the circle, not its radius.

Thus the probability is proportional to the square of radius. So now we need to figure out the random coordinates. In order to make the distribution not to depend on the size of the circle, or square of the radius, we need to re-scale the radius to the square root of a random number with uniform distribution.

Otherwise the points distribution is proportional to radius square, which is not uniform.

See the code below:

class Solution {
public:
    Solution(double radius, double x_center, double y_center) {
        rad = radius;
        x0 = x_center;
        y0 = y_center;
    }

    vector<double> randPoint() {
        double th = uniform()*PI*2;
        double r = rad*sqrt(uniform());//the key
        double x = x0 + r*cos(th), y = y0 + r*sin(th);
        return {x, y};
    }

private:
    double rad, x0, y0, PI = 3.1415926;
    double uniform() {
        return (double)rand()/RAND_MAX;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */