algorithm - 一组坐标形成的矩形面积之和

Question

我得到了一组 N 个二维坐标。将

的所有可能的 2 组合配对

坐标，那么我们可以组成N * (N - 1)/2个平行于的矩形

两个轴，两个点是相邻的顶点。现在我需要找到

这些矩形的面积之和，其中暴力破解(即迭代

通过所有组合)给出 TLE。所以到目前为止我最好的尝试是:

For example, if N = 5, then for all coordinates (xi, yi) where 0 <= i < N:

the sum of rectangle areas would be

(x0 - x1) * (y0 - y1) +
(x0 - x2) * (y0 - y2) +
          .
          .
          .
(x3 - x4) * (y3 - y4)

=

x0y0 + x1y1 - x0y1 - x1y0 +
x0y0 + x2y2 - x0y2 - x2y0 +
            .
            .
            .
x3y3 + x4y4 - x3y4 -x4y3

=

(N-1) * (x0y0 + x1y1 + x2y2 + x3y3 + x4y4) -
x0 * (y1 + y2 + y3 + y4) -
x1 * (y0 + y2 + y3 + y4) -
x2 * (y0 + y1 + y3 + y4) -
x3 * (y0 + y1 + y2 + y4) - 
x4 * (y0 + y1 + y2 + y3)

we can calculate the sum of y coordinates while input,

then we can get the last four terms by simply subtracting the corresponding y coordinate 

of the coefficient (x0 ~ x4).

Thus, all five terms can be calculated with O(n) time complexity.

然后我发现了一个重大缺陷，这让我很失望:

这在 x0 > x1, y1 > y0(或任何其他两个坐标)时不起作用，

这个矩形的面积变成了x0y1 + x1y0 - x0y0 -x1y1,

这与我的方法中的形式不同。

这个问题有没有可能的解决方案(当然，不抽时间

复杂度 O(n^2) ), 或者这个算法实际上是一个完整的

不同的？

编辑:内存使用不是问题

编辑 2:坐标可以重复，或者具有相同的 x(y) 值。在这种情况下，面积为 0

Answer 1

您给定的问题可以在 O(n*log(n)) 时间复杂度内解决，下面是我们如何解决它:

让我们固定一个点 (x₀, y₀)，我们想为其计算所有可能的矩形的总和，这些矩形可以使用该点制定。

同样的公式是:

对于所有 x_i 和 y_i 其中，(x₀ ≥ x_i && y₀ ≥ y_i), 公式可以简单分解为

= ∑ (x₀y₀ +x_iy_i) - (x_iy₀ + x₀x _我)

现在让我们讨论如何在 O(log(n)) 中计算公式的每个组件。

• x₀y₀ ~ 这只是当前点的乘积，可以在 O(1) 中轻松计算
• x_iy_i ~ 所有满足 x₀ ≥ x_i && y₀ ≥ y_i。适合查询这种图形的数据结构可以是二维二叉索引树(BIT)或二维分段树。这是一个美丽的数据结构，我真的建议您在线阅读它。在给定的场景中，我更喜欢 2D BIT，因为它们更容易编码。我的一个实现的链接在这里:https://github.com/nileshsah/advanced-data-structures/blob/master/2d_Binary_Indexed_Tree.cpp
• x_iy₀ ~ 这是 y₀ 乘以所有 x_i 这样的总和y_i ≤ y₀ 和 x_i ≤ x₀，为此我们可以维护另一个 2D BIT给定 x-y 范围内所有 x_i 的总和。然后我们可以在 O(log(n)) 中检索这个值
• x₀y_i ~ 这是 x₀ 乘以所有 y_i 这样的总和x_i ≤ x₀ 和 y_i ≤ y₀，为此我们维护不同的 2D BIT给定 x-y 范围内所有 y_i 的总和。然后我们可以在 O(log(n)) 中检索这个值

对于所有其他情况，我们只需要根据与上述每个组件相关的符号和使用前缀和数组或二维 BIT 树。

如果需要，我愿意解释更多。希望这为您提供了一个很好的起点来解决您给定的问题。干杯! :)