Count number of circle intersections - PrismoSkills

Count number of circle intersections - PrismoSkills

Count number of circle intersections Problem: Given an array of integers where array[i] represents the radius of a circle at point (0,i) Find the number of intersections of all the circles formed by the above array. Example: If given array is [2,1,3], then 3 circles would be formed whose end-points would be: [-2,2], [0,2] and [-1,5] Solution: An O(n2) solution can be done very simply using the following properties: (Assuming R ): Two circles do not intersect if their centers are more than R 1 + R 2 Two circles intersect once if their centers are exactly R 1 + R 2 distance apart. Two circles intersect twice if their centers are less than R 1 + R 2 Two circles intersect once if their centers are exactly R 1 - R 2 distance apart. Two circles do not intersect if their centers are less than R 1 - R 2 distance apart. Using the above properties, compare each circle with rest of the circles and count the number of intersections.

Read full article from Count number of circle intersections - PrismoSkills