CODEWITHSUNDEEP
algorithmdata-structures
user2040997
user2040997

Reputation: 373

Counting total number of points inside 2 circles

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?

Upvotes: 5

Views: 825

Answers (2)

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

Solution with O(log2N) 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 (1012 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 log2N).

Upvotes: 4

Bruno Reis
Bruno Reis

Reputation: 37832

Let C1, C2 be the centers of the disks. Let Pi, i = 1 ... n, be the points. Let Qj, j = 1 ... q, be the j-th query, Qj = (qj1, qj2).

  1. For each point Pi, calculate d(Pi, Ck), k = 1 or 2. Put it in a sorted multimap: Mk(d(Pi, Ck)) contains Pi. This can be done in O(nlogn) (this is actually just like sorting the list of distances).
  2. For each query Qj, do a binary search for qjk on the keys of Mk, which can be done in O(logn).
  3. For each query Qj, take the union of the values of the multimap on the keys which are less then or equal to the one you found above.

Upvotes: 2

Related Questions