Sponsored
Sponsored
Rejection sampling is a technique used to generate samples from a distribution by generating samples from a proposal distribution and then rejecting some of the samples. In the context of this problem, you can generate random points in a square that circumscribes the circle and then only accept those points that lie inside the circle.
Time Complexity: O(1) on average. Space Complexity: O(1) as no extra space is used.
1#include <random>
2#include <vector>
3#include <cmath>
4
5class Solution {
6 double radius, x_center, y_center;
7 std::default_random_engine generator;
8 std::uniform_real_distribution<double> distribution;
9
10public:
11 Solution(double radius, double x_center, double y_center) : radius(radius), x_center(x_center), y_center(y_center), distribution(-radius, radius) {}
12
13 std::vector<double> randPoint() {
14 double x, y;
15 do {
16 x = distribution(generator);
17 y = distribution(generator);
18 } while (x * x + y * y > radius * radius);
19 return {x_center + x, y_center + y};
20 }
21};This C++ solution mirrors the approach in Python, using the C++ Standard Library’s random utilities to generate points within a bounding square, ensuring uniform distribution inside the circle using rejection sampling.
Instead of generating points in a square and rejecting those outside the circle, we can directly generate points within the circle using polar coordinates. By randomly selecting an angle and a distance from the center, and then converting these polar coordinates to Cartesian coordinates, we can efficiently generate a uniform random point within the circle.
Time Complexity: O(1). Space Complexity: O(1).
1import java.util.Random;
2
3
This Java solution utilizes polar coordinates to generate a point by first determining a random angle and a random radial distance (scaled correctly) within the circle. The radial distance is the square root of a random number between 0 and 1 multiplied by the circle's radius to ensure uniform distribution.