← 返回题目列表

AtCoder · abc318_b

D. 重叠的纸张

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

有 N 矩形薄片在坐标平面上展开。

每张纸覆盖的矩形区域的每条边都平行于 x- 或 y- 轴。
具体来说, i第一张纸恰好覆盖了满足条件的区域 A_i \leq x\leq B_i 和 C_i \leq y\leq D_i.

让 S 是面积 由一张或多张纸覆盖的区域。可以证明 S 是约束下的整数。
打印 S 作为整数。

约束

  • 2\leq N\leq 100
  • 0\leq A_i<B_i\leq 100
  • 0\leq C_i<D_i\leq 100
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N

输出

打印区域 S 被一张或多张纸覆盖的区域作为一个整体。


示例输入 1

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

示例输出 1

20

这三张纸覆盖以下区域。
这里,红色、黄色和蓝色分别代表第一张、第二张和第三张纸覆盖的区域。

因此,被一张或多张纸覆盖的区域的面积为 S=20.


示例输入 2

2
0 100 0 100
0 100 0 100

示例输出 2

10000

请注意,不同的工作表可能覆盖相同的区域。


示例输入 3

3
0 1 0 1
0 3 0 5
5 10 0 10

示例输出 3

65