What is the maximum number of points in which 10 straight lines can intersect 5 circles

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

Given two integers X and Y, the task is to find the maximum number of points of intersection possible among X circles and Y straight lines.

Example:  

Input: X = 4, Y = 4 
Output: 50 
Explanation: 
4 lines intersect each other at 6 points and 4 circles intersect each other at maximum of 12 points. 
Each line intersects 4 circles at 8 points. 
Hence, 4 lines intersect four circles at a maximum of 32 points. 
Thus, required number of intersections = 6 + 12 + 32 = 50.

Input: X = 3, Y = 4 
Output: 36 
 

Approach: 
It can be observed that there are three types of intersections:  

1. The number of ways to choose a pair of points from X circles is 
   . Each such pair intersect at most two points.
2. The number of ways to choose a pair of points from Y lines is 
   
   . Each such pair intersect in at most one point.
3. The number of ways to choose one circle and one line from X circles and Y lines is is 
   . Each such pair intersect in at most two points. 

So, the maximum number of point of intersection can be calculated as: 
=> 

=> 

 

Thus, formula to find maximum number of point of intersection of X circles and Y straight lines is: 

Below is the implementation of the above approach:  

C++

#include

using namespace std;

int maxPointOfIntersection(int x, int y)

{

    int k = y * (y - 1) / 2;

    k = k + x * (2 * y + x - 1);

    return k;

}

int main()

{

    int x = 3;

    int y = 4;

    cout << (maxPointOfIntersection(x, y));

}

Java

class GFG{

static int maxPointOfIntersection(int x, int y)

{

    int k = y * (y - 1) / 2;

    k = k + x * (2 * y + x - 1);

    return k;

}

public static void main(String[] args)

{

    int x = 3;

    int y = 4;

    System.out.print(maxPointOfIntersection(x, y));

}

}

Python3

def maxPointOfIntersection(x, y):

    k = y * ( y - 1 ) // 2

    k = k + x * ( 2 * y + x - 1 )

    return k

x = 3

y = 4

print(maxPointOfIntersection(x, y))

C#

using System;

class GFG{

static int maxPointOfIntersection(int x, int y)

{

    int k = y * (y - 1) / 2;

    k = k + x * (2 * y + x - 1);

    return k;

}

public static void Main(String[] args)

{

    int x = 3;

    int y = 4;

    Console.Write(maxPointOfIntersection(x, y));

}

}

Javascript

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