Counting total number of points inside 2 circles

Question

There are 2 circles and their centers are fixed and will be given as input. Then there will be n points, the x and y co-ordinates of which are given as input.

Finally, there will be q queries. For each query, the radius of the two circles (Let them be r1 and r2) will be given. Output the total number of points inside the first circle or the second circle for each query. A point lies inside a circle if the distance from the point to the center is less than or equal to the radius of the circle.

Constraints: n, q <= 10^6 r1,r2 <= 10^7 and for each co-ordinate, |x| and |y| <= 10^6

I'm looking for a O(nlogn) or O(nlog^2n) preprocessing and then O(logn) algorithm per query. O(n) solution per query is too slow. Any ideas how to crack this?

Answer 1

Solution with O(log²N) query time.

1. It is easier for each query to count the points outside of both circles, then subtract the result from total number of points.
2. It is easier to use Cartesian coordinates. So that X would be the distance from C1, Y - the distance from C2. In this case we only need to find number of points in the area X > r1 && Y > r2.
3. Assign value "1" to each point. Now we only need to find sum of the values in given area. In 1D case this may be done with Fenwick tree. But 2D case is not much different if 2D Fenwick tree is used.
4. 2D Fenwick tree should occupy too much space (10¹² values with given constraints). But 2D array for Fenwick tree is very sparse, so we could use a hash map to store its values and decrease space requirements (and pre-processing time) to O(N log²N).