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*

Auto comment: topic has been updated by rawat_sidharth (previous revision, new revision, compare).First observation:0 $$$\leq$$$p$$$\leq$$$ 50, means that there are at most 51 different radiuses.Second observation:if we're looking at a circle of radiusr, let's try to add all the circles with some fixed radiusR, such thatr$$$\leq$$$R, and those circles intersect. There are at most 3 groups which circles of radiusRcan form. So let's just find at least one circle in each group and get an edge between. After that it's just DFS, with $$$O(n)$$$ vertices and $$$O(np)$$$ edges.Now let's link 4 circles that are in 4 different parts of the coordinate plane using some data structure like segment tree.

N̶o̶w̶ ̶i̶f̶ ̶i̶'̶v̶e̶ ̶m̶i̶s̶u̶n̶d̶e̶r̶s̶t̶o̶o̶d̶ ̶t̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶a̶n̶d̶ ̶t̶w̶o̶ ̶c̶i̶r̶c̶l̶e̶s̶ ̶i̶n̶t̶e̶r̶s̶e̶c̶t̶ ̶i̶f̶ ̶**d̶i̶s̶t̶** ̶≤̶ ̶**r̶** ̶+̶ ̶**R̶**,̶ ̶t̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶i̶s̶ ̶i̶n̶d̶e̶e̶d̶ ̶s̶o̶l̶v̶e̶d̶ ̶i̶n̶ $$$O(np \cdot log)$$$.

Otherwise:R—r$$$\leq$$$dist$$$\leq$$$r+RThird observation:if there is a circle of radiusRand the circle of radiusrinside of it, then the circle of radiusRintersects all the circles of radiusR, such that they intersect or contain the circle of radiusr.Now we should link the circles only in case if there is at least one circle of radius

Rthat intersects with ours. So to link correctly we need to know, whether there is such a circle. This is where it gets really hard and I don't know any nice solution (the best I can do is probably $$$O(np^2log)$$$ or $$$O(np^2)$$$ which is way too slow), so it'sunsolved.UPD:I was a little wrong, so I still can't figure out the solution.thanks for the insights :)

Are x, y, and r reals or integers?

I don't think it really matters.

x, y and r are all integers.