Recently encountered this problem in a competition. Tried solving it using graphs, creating neighbors and then finding the number of nodes in different disconnected sub-graphs. But the creation of neighbors itself is O(n^2) and hence was getting TLE. I have been trying to figure out a way to solve this without creating neighbors or find a more efficient way to create neighbors, but haven't been able to do so. I also thought of using union-find, but again computing distances between each pair is O(n^2). Any help would be really appreciated.

Problem:

There are n circles, for each of which center ( x , y ) and radius r are provided. These circles can intersect each other. Circles are said to be intersecting if they touch each other or cross each other's circumference. A cluster of circles is defined as a group of circles which are in contact with each other. So, if C1 intersects C2 and C2 intersects C3, then C1, C2, C3 are in a cluster even if C1 and C3 don't directly intersect each other. We have to find the cluster with the largest number of circles. Print the number of circles in the largest cluster and the smallest circle index in that cluster. If 2 clusters have the same number of circles, print the one with the smallest circle index.

Constraints:

0<= n <= 1e5, 0 <= r <= 50, 0 <= x, y <= 1e4

Time limit:

3s for 50 test cases.

Additional info:

For 20% test cases, 0 <= n <= 100

For 30% test cases, 100 <= n <= 1000

For 30% test cases, 1000 <= n <= 1e4

For 20% test cases, 1e4 <= n <= 1e5