Last Updated: 17 Apr, 2021

Random point generator.

Moderate

Asked in companies

Solve now

Problem statement

Mr. Schrodinger recently developed a new hypothesis. For testing his hypothesis he needs some points inside a particular circle. For good testing, points should be uniformly distributed, i.e. evenly distributed inside the circle. So you as an assistant are asked to implement a random point generator function that will do the task.

More formally, you need to implement a function that will generate uniformly distributed random points inside the given circle.

Note:

A point on the circumference of a circle is considered an inner point.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains three space-separated integers ‘X’, ‘Y’, ‘R’ denoting x-coordinate, y-coordinate of the center of the circle and ‘R’ denoting the radius of the circle.

Output Format:

For each test case, the output will be 1, if you generated correct uniformly distributed points as described in the problem, else 0.

Note:

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
-10 ^ 9 <= X, Y <= 10 ^ 9
1 <= R <= 10 ^ 9

Time Limit: 1sec

Solve now

Approaches

01 Approach

The idea is to generate a random x-coordinate and y-coordinate and if it lies inside the circle, then return this point.

Algorithm:

Let the x-coordinate and y-coordinate of the center of a given circle be ‘Xc’ and ‘Yc’ and radius of the circle be ‘Rc’.
Run an infinite loop.
- Declare two double variables say ‘X’ and ‘Y’.
- Set ‘X’ and ‘Y’ to (random double value between -1 to 1) * ‘Rc’, this will ensure that ‘X’ and ‘Y’ individually do not exceed the radius of the circle, but the point (‘X’, ‘Y’) may lie outside the circle.
- If ‘X’ ^ 2 + ‘Y’ ^ 2 <= ‘Rc’ ^ 2 - this condition shows that point ( ‘X’, ‘Y’) lies inside the circle.
  - Return { ‘X’, ‘Y’ }.

Solve now

02 Approach

Any point on a circle can be described as a ( 'R', 'THETA') where 'R' is the distance of a point from the center of the circle and 'THETA' is the angle with the x-axis. To generate a random point inside a circle we can generate random 'R' and random 'THETA'. A key point to remember here is that to generate uniformly distributed points we want more points on a circle with a bigger area than a circle with a smaller area. As the area is proportional to the square of the radius. So Instead of generating uniform 'R' of all lengths, we want to generate more 'R' of bigger lengths.

For example for uniform distribution if 'R' with length must 1 is generated 4 times then 'R' with length ‘2’ should be generated 16 times, as the area it proportion to the square of 'R' i.e radius of the circle.

Algorithm:

Let the x-coordinate and y-coordinate of the center of a given circle be ‘Xc’ and ‘Yc’ and the radius of the circle be ‘Rc’.
Declare two float/decimal variables say 'R' and 'THETA'.
Generate and store a random double between 0 to 1 and take sqrt of the number as taking the square root of the number in range (0, 1) will make them greater by quadratic proportional.
Set 'R' = (generated random number ) * ‘R’.
Set 'THETA' = (random double value between 0 to 1) * 2 * Pi, to get a random angle between 0 to 360 degrees in radian form. Here, pi is the mathematical constant.
Declare two double variables say ‘X’ and ‘Y’.
Set ‘X’ to ‘Xc’ + R * cos(theta).
Set ‘Y’ to ‘Yc’ + R * sin(theta).
Return {‘X’, ‘Y’}.

Solve now