可以通过 扫线 算法完成。
我们将从左到右扫描一条假想线。我们将注意到直线和矩形集之间的交点表示一组间隔的方式，并且当我们遇到矩形的左边缘或右边缘时，它会发生变化。
假设交点在x坐标 x1 和 x2 之间不变。然后，如果经过的交点的长度 X1 是 大号 ，线会扫过的区域等于（ X2
- X1 ） 大号 ，通过从清扫 X1 至 X2* 。
例如，您可以在下一张图片中将 x1 视为左蓝色线，将 x1 视为右蓝色线（我从您那里偷走了，并进行了一些修改：））：
应该清楚的是，我们的 扫掠线 的交点在这些点之间没有变化。但是，蓝色相交与红色相交完全不同。
我们需要具有以下操作的数据结构：
insert_interval(y1, y2); get_total_length();
使用 段树 可以轻松实现这些功能，因此我现在不再赘述。
现在，该算法将如下所示：
- 取所有垂直线段，并按其x坐标对其进行排序。
- 对于每个相关的x坐标（仅显示为矩形边缘的x坐标很重要）：
- 令x1为先前的相关x坐标。
- 令x2为当前相关的x坐标。
- 令L为数据结构给出的长度。
- 将（x2-x1）* L加到总面积之和。
- 从数据结构中删除x = x2段的所有 右 边缘。
- 将所有x = x2段的 左 边缘添加到数据结构中。
由 左 及 右 我的意思是一个矩形的边。
该想法仅用于计算面积，但是，您可以对其进行修改以计算周长。基本上，您将想知道相交在某个x坐标处变化之前和之后的长度之间的差异。
该算法的复杂度为O（N log N）（尽管它取决于您可能会获得的输入值的范围，但这很容易解决）。
您可以在TopCoder上找到有关
扫线
算法的广泛主题的更多信息。
您可以在PEG评判Wiki上了解使用 段树的
各种方法。
这是我的算法（非常古老）的实现，作为SPOJ问题NKMARS的解决方案：实现。
