5

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?

4

2 回答 2

4

O(log 2 N) 查询时间的解决方案。

  1. 每个查询更容易计算两个圆圈之外的点，然后从总点数中减去结果。
  2. 使用笛卡尔坐标更容易。这样 X 将是与 C1 的距离，Y - 与 C2 的距离。在这种情况下，我们只需要找到该区域中的点数X > r1 && Y > r2。
  3. 为每个点分配值“1”。现在我们只需要找到给定区域中的值的总和。在一维情况下，这可以通过 Fenwick 树来完成。但是，如果使用 2D Fenwick 树，则 2D 情况并没有太大的不同。
  4. 2D Fenwick 树应该占用太多空间（10 12值具有给定的约束）。但是 Fenwick 树的二维数组非常稀疏，因此我们可以使用哈希映射来存储其值并将空间需求（和预处理时间）减少到 O(N log 2 N)。
于 2013-03-05T10:37:24.363 回答
2

设 C1、C2 为圆盘的中心。设 Pi, i = 1 ... n, 为点。令 Qj, j = 1 ... q, 是第 j 个查询，Qj = (qj1, qj2)。

  1. 对于每个点 Pi，计算 d(Pi, Ck)，k = 1 或 2。将其放入已排序的多重映射中：Mk(d(Pi, Ck)) 包含 Pi。这可以在 O(nlogn) 中完成（这实际上就像对距离列表进行排序）。
  2. 对于每个查询 Qj，在 Mk 的键上对 qjk 进行二分搜索，这可以在 O(logn) 中完成。
  3. 对于每个查询 Qj，将 multimap 的值与小于或等于上面找到的值的键合并。
于 2013-03-05T09:30:52.940 回答