根据某些标准从两个不同的集合中找到两个坐标之和的最快方法是什么？

Question

我有两套如下。从总和至少为 H 的每个集合中找到所有坐标的最佳方法是什么？

A = {(x1,y1), (x2,y2),....(xn,yn)}
B = {(p1,q1), (p2,q2),....(pn,qn)}

如果答案是 (x1,y1) 和 (p1,q1) 那么它应该满足 x1+p1>=H 和 y1+q1>=H。我需要找出所有这些坐标（仅计数）。

例子：

A = {(2,3), (1,6), (5,2), (10,1)}
B = {(5,6), (8,4), (3,5), (1,9), (7,7)}
H = 8
Answer: 7
Explanation:
    {
    {(1,6),(8,4)},
    {(1,6),(7,7)},        
    {(2,3),(7,7)},
    {(5,2),(5,6)},
    {(5,2),(7,7)},
    {(10,1),(1,9)},
    {(10,1),(7,7)}
    }

蛮力方法：我可以使用两个 for 循环来遍历两组 A 和 B 的所有组合。但这是 O(N^2) 解决方案。

我知道另一种技术，可以在 x 坐标上对集合 B 进行排序。这样我就可以从 A 中选取每个 x 坐标并在 B 中检查 Hx，识别 Hx 可以在 long n 中完成，但从那里我需要一一计数以检查 y 坐标是否满足条件或不是。

有没有更好的解决方案？

Answer 1

如果我是对的，范围树可以用来解决“主点计数”，即告诉 2D 集中有多少点具有坐标x>a并且y>b（参见 Shamos 和 Preparata，计算几何，第 40 页 + 第 2.3.4 节） ）。经过O(N Log N)一段时间的预处理和O(N Log N)存储后，可以及时回答查询O(Log\xc2\xb2N)。

\n\n

因此，通过依次尝试第二组的所有点并使用上述数据结构来计算第一组的点，使得 ，xj>h-pi，yj>h-qi您可以实现全局复杂度O(N Log\xc2\xb2N)。

\n