I thought of the problem for a complete 1 hour and could not come up with a solution. After that, I looked at the given sample test case and came up with a solution based on pure guesswork. Here is my approach:
Consider every pair of circles and try to find the 3rd circle which would match with the 2 circles following the properties given. Considering the first 2 circles as (x1,y1,r1) and (x2,y2,r2):
Find out two values value1 = (r1^2 + r2^2), value2 = (x1-x2)^2 + (y1-y2)^2
Here values1 is the sum of squares of the radii of the two circles and value2 is the square of the distance between the centers of the two circles.
If the 2 values are different there is no possible solution. If they are the same, then the radius of the third circle can be found out by the formula sqrt(value1/4). If this value is not an integer then again no possible solution. Otherwise, the final circle will have the following center and radius: ((x1+x2)/2, (y1+y2)/2, sqrt(value1/4)).
Now, finding the number of occurrences of such circles can be easily done by a map.
So, the total time complexity will be O(N^2Log(N)).
I don’t think this is the intended solution so thought I should share it. PS: I have no way to prove this is correct until now.