Samsung R&D Bangalore Question

There are n circles in a 2D plane. We are given their centers and radii. We have to find the largest connected component and print its size and index of smallest circle in that component.

Constraints :
n<=100000
center(a,b) : -10000 to 10000
1<=Radius <=100

Here is somewhat a rough idea:
You can use the Line Sweep algorithm to find the groups of intersecting circles in O(N.log(N)). If you then represent each groups using a disconnect components of a graph (consider circles as nodes). Then it would be easier to find the largest connected component and the smallest circle in that.
Check this out for finding intersecting circles using Line Sweep: algorithm - How to find and print intersections of n given circles in O(n*log(n)) time? - Stack Overflow

4 Likes