Well, you coul build a Voronoi diagram of the set of centers of circles, and then check every adjacent (by edges) pair of circles in the diagram (O(n)), just check that the sum of radious is the same as the distance between the center, if radii are integer such a check can even be made in integers.

Now it appears to me that no circle Y con be ok for a circle X if it isn't its neighbour, without violating the property of only one point of intersection with some neighbour of X.

Of course writing a voronoi working in time for 500000 points may prove challenging, so if you do that, you let me see your code after that, I've never implemented O(nlogn) Voronoi myself :)

Sorry in advance if there is any mistake with this solution, and perhaps there is a simpler solution.

It is a quite standard sweep line problem.

Sweep with a vertical line from left to right. There are 2 types of events: a circle began, a circle ended.

Maintain a set of circles that the line currently intersects (began, but not ended). In this set, maintain them sorted by Y coordinate of their center. Then each time you add a circle, you only need to check at most 2 of it's neighbors (for having a common point with it). The same when you delete a circle, there could be at most one new pair of neighbors formed that you need to check.

What you have to be careful with:

1. counting the same pair twice (happens when you delete circles from the set).
2. not counting circles sharing a common point that have the same Y. To count them, you should process adding events before the removal events when tie-breaking equal X coordinates.