Geek asks and answers

Counting the total number of points within 2 circles

There are 2 circles, and their centers are fixed and will be entered as input. Then there will be n points whose x and y coordinates are given as input.

Finally, there will be q queries. For each request, the radius of two circles will be set (let them be r1 and r2). Print the total number of points inside the first circle or 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.

Limitations: n, q <= 10 ^ 6 r1, r2 <= 10 7 and for each coordinate | x | and | y | <= 10 ^ 6

I am looking for preprocessing O (nlogn) or O (nlog ^ 2n), and then the O (logn) algorithm for each request. The O (n) solution for the request is too slow. Any ideas how to hack this?

+5
source share
2 answers

Solution with O (log 2 N) query time.

  • For each query, it’s easier to count points outside both circles, and then subtract the result from the total number of points.
  • Easier to use Cartesian coordinates. So X is the distance from C1, Y is the distance from C2. In this case, we need to find only the number of points in the area X > r1 && Y > r2.
  • Assign a value of "1" to each point. Now we need to find the sum of the values ​​in this area. In the case of 1D, this can be done with the Fenwick tree. But the 2D code is not much different if the Fenwick 2D tree is used.
  • 2D (10 12 ). 2D- Fenwick , - ( ) O (N log 2 N).
+4

C1, C2 - . Pi, = 1... n, - . Qj, j = 1... q, - j- , Qj = (qj1, qj2).

  • Pi d (Pi, Ck), k = 1 2. : Mk (d (Pi, Ck)) Pi. O (nlogn) ( , ).
  • Qj qjk Mk, O (logn).
  • Qj , , .
+2

More articles:


All Articles