寻找 O(nlogn) alg 来计算坐标距离大于特定值的点对

Question

给定输入n个点(x_i，y_i(，其中x_i，y_i\in 1..n \forall i。谁能启发我构建一个 O(nlogn( 算法来计算点对 (i，j( 的想法，其中 |x_i-x_j|>=a && |y_i-y_j|>=b。一个很好的假设可以是 a=b=n/2。

感谢您的帮助。

Answer 1

首先，让我们尝试计算出 |x_i-x_j|

当然，只需将每个插入处缓冲区的大小相加即可告诉我们有多少对满足 |x_i-x_j| <a，类似的过程将告诉我们有多少对满足><b。>

每对都属于四类之一，我们现在知道的足以将它们全部计算出来。我们知道(X-close和Y-close(的大小。我们知道 X-close 的大小，所以我们知道 (X-close，但不是 Y-close( 的大小。同样，我们知道 Y 接近的大小，所以我们知道(不是 X-关闭而是 Y-关闭(的大小。这是四个可能类别中的三个，我们知道如果有 N 个点，就有 N*(N-1(/2 对，所以我们可以减去其他三个类别的大小来得到(不是 X-close 和 Y-close(的大小，这当然是你要求的。