Random point generator.

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in companies
FacebookTrilogy Innovations

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
0 0 1
1 1 1

Sample Output 1:

1
1

Explanation of Sample Input 1:

Test case 1:
Random function must generate any random point inside the circle with center at (0, 0) and radius 1. For example 3 generated points can be [(0.2, 0.05), (-0.7, 0.32), (-0.11, -0.23)]. 

Test case 2:
Randomly generated 3 points can be [(1.3, 1.07), (1, 0), (0, 1)].

Sample Input 2:

1
0 0 10

Sample Output 2:

1

Explanation of Sample Input 2:

Test case 1:
Randomly generated 3 points can be [(9.3, 0.002), (1.4, -2.0), (-1.99, 3.33 )].
Hint

Generate a random point and check if it is inside the circle or not.

Approaches (2)
Rectangular coordinates

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’ }.
Time Complexity

O(1)

 

Although we are using an Infinite loop but random function will generate the desired point in constant time. Hence the overall time complexity is constant.

Space Complexity

O(1)

 

As we are not using any extra space.

Code Solution
(100% EXP penalty)
Random point generator.
Full screen
Console