Random point generator.
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

Question

Random point generator.

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

Accepted Answer

Let y be the smallest integer such that 2^y >= N.

So, we will call G(y) till we get a number in the desired range.

Follow-up - Expected Number of calls to G before we get a number in the desired range.

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1)

As we are not using any extra space.

Time Complexity: O(1)Explanation:

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.

C++ (g++ 5.4)

/*
    Time Complexity: O(1)
    Space Complexity: O(1)
*/

vector randomPoint(double radius, double xc, double yc)
{
    // Declare two varaible to store random points inside circle.
    double x, y;

    while(true)
    {
        // Declare two varaibles to store a random value between -1 to 1.
        double rand1,rand2;
        rand1 = (2 * ((double)rand() / RAND_MAX) - 1.0);
        rand2 = (2 * ((double)rand() / RAND_MAX) - 1.0);

        x = rand1 * radius;
        y = rand2 * radius;

        // If the current point lies inside the circle, then break the loop.
        if (x * x + y * y <= radius * radius)
        {
            break;
        }

    }
    
    // Return point.
    return { xc + x, yc + y };
}

Python (3.5)

'''
    Time Complexity: O(1)
    Space Complexity: O(1)
'''

import random

def randomPoint(radius, xc, yc):

    # Declare two varaible to store random points inside circle.
    x = 0 
    y = 0

    while True:
        # Declare two varaibles to store a random value between -1 to 1.
        rand1 = (2 * (random.uniform(0,1)) - 1.0)
        rand2 = (2 * (random.uniform(0,1)) - 1.0)

        x = rand1 * radius
        y = rand2 * radius

        # If the current point lies inside the circle, then break the loop.
        if (x * x + y * y <= radius * radius):
            break
        
    # Return point.
    return [xc + x, yc + y]

Java (SE 1.8)

/*
    Time Complexity: O(1)
    Space Complexity: O(1)
*/
    
import java.util.ArrayList;

public class Solution {
	
	public static ArrayList randomPoint(double radius, double xc, double yc) {
		// Declare two varaible to store random points inside circle.
	    Double x, y;

	    while(true)
	    {
	        // Declare two varaibles to store a random value between -1 to 1.
	        Double rand1,rand2;
	        rand1 = (2 * (Double)Math.random()  - 1.0);
	        rand2 = (2 * (Double)Math.random()  - 1.0);
	        
	        x = rand1 * radius;
	        y = rand2 * radius;

	        // If the current point lies inside the circle, then break the loop.
	        if (x * x + y * y <= radius * radius)
	        {
	            break;
	        }

	    }
	    
        ArrayList sol = new ArrayList();
        sol.add(xc+x);
        sol.add(yc+y);
	    // Return point.
	    return sol;
	}
}

Accepted Answer

Polar coordinates

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

Space Complexity: O(1)Explanation:

O(1)

As we are not using any extra space.

Time Complexity: O(1)Explanation:

O(1)

As we are not using any loop. Hence the overall time complexity is constant.

C++ (g++ 5.4)

/*
    Time Complexity: O(1)
    Space Complexity: O(1)
*/

#include

vector randomPoint(double radius, double xc, double yc)
{
    // Declare two variable to store random points inside circle.
    double x, y;

    // Declare a variable 'theta' to store a random angle in range 0 to 2 * PI, i.e. (0 to 360).
    double theta = (double)rand() / RAND_MAX * 2 * M_PI;

    // Declare a variable 'r' to store a distance from centre of random point. 
    double r = sqrt((double)rand() / RAND_MAX) * radius;

    // Set both point according to trigonometry.
    x = cos(theta) * r,
    y = sin(theta) * r;

    // Return point.
    return { xc + x, yc + y };
}

Python (3.5)

'''
    Time Complexity: O(1)
    Space Complexity: O(1)
'''

import math
import random

def randomPoint(radius, xc, yc):

    # Declare a variable 'theta' to store a random angle in range 0 to 2 * PI, i.e. (0 to 360).
    theta = random.uniform(0, 1) * 2 * math.pi

    # Declare a variable 'r' to store a distance from centre of random point.
    r = math.sqrt(random.uniform(0, 1)) * radius

    # Set both point according to trigonometry.
    x = math.cos(theta) * r
    y = math.sin(theta) * r

    ans = [xc + x, yc + y]

    # Return point.
    return ans

Java (SE 1.8)

/*
    Time Complexity: O(1)
    Space Complexity: O(1)
*/
    
import java.util.ArrayList;

public class Solution {
	
	public static ArrayList randomPoint(double radius, double xc, double yc) {
		// Declare two variable to store random points inside circle.
	    Double x, y;

	    // Declare a variable 'theta' to store a random angle in range 0 to 2 * PI, i.e. (0 to 360).
	    double theta = (Double)Math.random() * 2 * Math.PI;

	    // Declare a variable 'r' to store a distance from centre of random point. 
	    Double r = Math.sqrt((Double)Math.random()) * radius;

	    // Set both point according to trigonometry.
	    x = Math.cos(theta) * r;
	    y = Math.sin(theta) * r;

	    ArrayList sol = new ArrayList();
        sol.add(xc+x);
        sol.add(yc+y);
	    // Return point.
	    return sol;
	}
}

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

Note:

Input Format:

Output Format:

Note:

Constraints:

Algorithm:

Top Trilogy Innovations Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern