Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/478.html

478. Generate Random Point in a Circle (Medium)

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.

Companies:
Leap Motion

Related Topics:
Math, Random, Rejection Sampling

Similar Questions:

Solution 1. Rejection Sampling

See explanations here

// OJ: https://leetcode.com/problems/generate-random-point-in-a-circle/
// Time: O(1)
// Space: O(1)
// Ref: https://leetcode.com/problems/generate-random-point-in-a-circle/solution/
class Solution {
private:
    double radius, x_center, y_center, area;
    mt19937 rng{random_device{}()};
    uniform_real_distribution<double> uni{0, 1};
public:
    Solution(double radius, double x_center, double y_center) : radius(radius), x_center(x_center), y_center(y_center) {
    }
    
    vector<double> randPoint() {
        double x0 = x_center - radius;
        double y0 = y_center - radius;
        while (true) {
            double x = x0 + uni(rng) * 2 * radius;
            double y = y0 + uni(rng) * 2 * radius;
            if (sqrt(pow(x - x_center, 2) + pow(y - y_center, 2)) > radius) continue;
            return { x, y };
        }
    }
};

Solution 2. Inverse Transform Sampling (Math)

// OJ: https://leetcode.com/problems/generate-random-point-in-a-circle/
// Time: O(1)
// Space: O(1)
// Ref: https://leetcode.com/problems/generate-random-point-in-a-circle/solution/
class Solution {
private:
    double radius, x_center, y_center, area;
    mt19937 rng{random_device{}()};
    uniform_real_distribution<double> uni{0, 1};
public:
    Solution(double radius, double x_center, double y_center) : radius(radius), x_center(x_center), y_center(y_center) {
    }
    vector<double> randPoint() {
        double d = radius * sqrt(uni(rng)), theta = uni(rng) * 2 * M_PI;
        return { x_center + d * cos(theta), y_center + d * sin(theta) };
    }
};

  • class Solution {
    double radius;
    double x_center;
    double y_center;

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
    }
    
    public double[] randPoint() {
        double radian = Math.random() * 2 * Math.PI;
        double curRadius = Math.sqrt(Math.random()) * radius;
        double x = x_center + curRadius * Math.cos(radian);
        double y = y_center + curRadius * Math.sin(radian);
        double[] point = {x, y};
        return point;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(radius, x_center, y_center);
 * double[] param_1 = obj.randPoint();
 */

  • // OJ: https://leetcode.com/problems/generate-random-point-in-a-circle/
// Time: O(1)
// Space: O(1)
// Ref: https://leetcode.com/problems/generate-random-point-in-a-circle/solution/
class Solution {
private:
    double radius, x_center, y_center;
    mt19937 rng{random_device{}()};
    uniform_real_distribution<double> uni{0, 1};
public:
    Solution(double radius, double x_center, double y_center) : radius(radius), x_center(x_center), y_center(y_center) {
    }
    
    vector<double> randPoint() {
        double x0 = x_center - radius;
        double y0 = y_center - radius;
        while (true) {
            double x = x0 + uni(rng) * 2 * radius;
            double y = y0 + uni(rng) * 2 * radius;
            if (sqrt(pow(x - x_center, 2) + pow(y - y_center, 2)) > radius) continue;
            return { x, y };
        }
    }
};

  • class Solution:

    def __init__(self, radius, x_center, y_center):
        """
        :type radius: float
        :type x_center: float
        :type y_center: float
        """
        self.r = radius
        self.x = x_center
        self.y = y_center

    def randPoint(self):
        """
        :rtype: List[float]
        """
        nr = math.sqrt(random.random()) * self.r
        alpha = random.random() * 2 * 3.141592653
        newx = self.x + nr * math.cos(alpha)
        newy = self.y + nr * math.sin(alpha)
        return [newx, newy]
        


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

All Problems

All Solutions