P1389. 简单多边形的面积

问题描述

在二维$xy$ 平面上有 $N$ 个矩形$$（1 ≤ N ≤ 1,000）$$。矩形的四条边是水平或垂直的线段。矩形由其左下角和右上角的点定义。每个角点是一对非负整数，表示其 $x$ 和 $y$ 坐标，范围为 $0$ 到 $50,000$。

假设它们并集的轮廓由一组线段$S$ 定义。我们可以使用 $S$ 的子集来构造简单多边形。请报告由 $S$ 的子集构造的多边形的总面积。面积应尽可能大。在二维 $xy$ 平面上，多边形由有限的线段集合定义，使得每条线段的端点恰好被两条边共享，且没有边的子集具有相同的性质。线段是边，它们的端点是多边形的顶点。如果不存在一对非连续的边共享一个点，则多边形是简单的。

示例：考虑以下三个矩形：

• 矩形 $$1：<(0, 0) (4, 4)>$$
• 矩形 $$2：<(1, 1) (5, 2)>$$
• 矩形 $$3：<(1, 1) (2, 5)>$$

由这些矩形构造的所有简单多边形的总面积是 18。

输入

输入包含多个测试用例。每个测试用例由一行四个 $-1$ 分隔。输入的结尾是一行四个 $-1$。每个测试用例中的矩形逐行给出。每个矩形一行，包含四个非负整数。前两个是左下角的 $x$ 和 $y$ 坐标，接下来两个是右上角的 $x$ 和 $y$ 坐标。

输出

对于每个测试用例，输出一行，表示所有简单多边形的总面积。

输入示例 1

0 0 4 4
1 1 5 2
1 1 2 5
-1 -1 -1 -1
0 0 2 2
1 1 3 3
2 2 4 4
-1 -1 -1 -1
-1 -1 -1 -1

输出示例 1

18
10

来源

Taiwan 2001