可以通过 扫线 算法完成。

我们将从左到右扫描一条假想线。我们将注意到直线和矩形集之间的交点表示一组间隔的方式，并且当我们遇到矩形的左边缘或右边缘时，它会发生变化。

假设交点在x坐标 x1 和 x2 之间不变。然后，如果经过的交点的长度 X1 是 大号 ，线会扫过的区域等于（ X2
- X1 ） 大号 ，通过从清扫 X1 至 X2* 。

例如，您可以在下一张图片中将 x1 视为左蓝色线，将 x1 视为右蓝色线（我从您那里偷走了，并进行了一些修改：））：

应该清楚的是，我们的 扫掠线 的交点在这些点之间没有变化。但是，蓝色相交与红色相交完全不同。

我们需要具有以下操作的数据结构：

insert_interval(y1, y2); 
get_total_length();

使用 段树 可以轻松实现这些功能，因此我现在不再赘述。

现在，该算法将如下所示：

1. 取所有垂直线段，并按其x坐标对其进行排序。
2. 对于每个相关的x坐标（仅显示为矩形边缘的x坐标很重要）：
   • 令x1为先前的相关x坐标。
   • 令x2为当前相关的x坐标。
   • 令L为数据结构给出的长度。
   • 将（x2-x1）* L加到总面积之和。
   • 从数据结构中删除x = x2段的所有 右 边缘。
   • 将所有x = x2段的 左 边缘添加到数据结构中。

由 左 及 右 我的意思是一个矩形的边。

该想法仅用于计算面积，但是，您可以对其进行修改以计算周长。基本上，您将想知道相交在某个x坐标处变化之前和之后的长度之间的差异。

该算法的复杂度为O（N log N）（尽管它取决于您可能会获得的输入值的范围，但这很容易解决）。

您可以在TopCoder上找到有关
扫线
算法的广泛主题的更多信息。

您可以在PEG评判Wiki上了解使用 段树的
各种方法。

这是我的算法（非常古老）的实现，作为SPOJ问题NKMARS的解决方案：实现。