Here's an implementation in Javascript using vectors. The code is well documented, you should be able to follow it. Here's the original source
See live demo here:
Given a number n, we need to find the maximum number of times n circles intersect.
Input : n = 2
Output : 2Input : n = 3
Output : 6
As we can see in above diagram, for each pair of circles, there can be maximum two intersection points. Therefore if we have n circles then there can be nC2 pairs of circles in which each pair will have two intersections. So by this, we can conclude that by looking at all possible pairs of circles the mathematical formula can be made for the maximum number of intersections by n circles is given by 2 * nC2.
2 * nC2 = 2 * n * (n – 1)/2 = n * (n-1)
#include <bits/stdc++.h> using namespace std; int intersection(int n) { return n * (n - 1); } int main() { cout << intersection(3) << endl; return 0; } |
import java.io.*; public class GFG { static int intersection(int n) { return n * (n - 1); } public static void main(String[] args) throws IOException { System.out.println(intersection(3)); } } |
def intersection(n): return n * (n - 1); print(intersection(3)) |
using System; class GFG { static int intersection(int n) { return n * (n - 1); } public static void Main() { Console.WriteLine(intersection(3)); } } |
<?php function intersection($n) { return $n * ($n - 1); } echo intersection(3); ?> |
<script> function intersection(n) { return n * (n - 1); } document.write(intersection(3)); </script> |
Time Complexity: O(1)
Auxiliary Space: O(1)
Easy solution is to consider another plane such that the centers are along an axis.
Given the points $(x_1,y_1)$ and $(x_2,y_2)$. We focus on the center point of both circles given by $$ \left( \frac{x_1+x_2}{2}, \frac{y_1+y_2}{2} \right). $$
The distance between the centers of the circles is given by $$ R = \sqrt{ (x_2-x_1)^2 + (y_2-y_1)^2}. $$
We can consider the following orthogonal vectors $$ \vec{a} = \left( \frac{x_2-x_1}{R}, \frac{y_2-y_1}{R} \right), \vec{b} = \left( \frac{y_2-y_1}{R}, - \frac{x_2-x_1}{R} \right). $$
In the $(\vec{a},\vec{b})$ plane we get the equations $$ \big( a + R / 2 \big)^2 + b^2 = r_1^2,\\ \big( a - R / 2 \big)^2 + b^2 = r_2^2. $$
Whence $$ a = \frac{r_1^2 - r_2^2}{2R},\\ b = \pm \sqrt{ \frac{r_1^2+r_2^2}{2} - \frac{(r_1^2-r_2^2)^2}{4R^2} - \frac{R^2}{4}}. $$ The intersection points are given by $$ (x,y) = \frac{1}{2} \big( x_1+x_2, y_1+y_2 \big) + \frac{r_1^2 - r_2^2}{2R^2} \big( x_2-x_1, y_2-y_1 \big)\\ \pm \frac{1}{2} \sqrt{ 2 \frac{r_1^2+r_2^2}{R^2} - \frac{(r_1^2-r_2^2)^2}{R^4} - 1} \big( y_2-y_1, x_1-x_2 \big), $$ where $R$ is the distance between the centers of the circles.