2023 蓝桥杯热身赛

Problem P19. 房屋面积(25 分)

Tom 和 Jerry 环球旅行归来以后,决定重新盖一座房子。

他们找到一片空地,商量着哪块区域是走廊、客厅、沙发、阳台、书房、办公桌等等,这些区域都是矩形,而且可能会出现部分或全部重叠。

他们认为这些矩形区域的并集才是房屋的 “有效功能区”,请你帮他们算算 “有效功能区” 的周长是多少。

输入

第一行包含一个整数 n(0\leq n\leq 5000) ,表示矩形的个数。

接下来 n 行,每行四个整数 x_1,y_1,x_2,y_2(-10000\leq x_1,y_1,x_2,y_2\leq 10000) ,其中 (x_1,y_1) 表示矩形的左下角坐标, (x_2,y_2) 表示矩形的右上角坐标。

数据保证每个矩形的面积至少为 1

输出

输出一个整数,表示矩形区域的并集的周长。

样例

标准输入 复制文本
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
标准输出 复制文本
228

提示

样例中的矩形如下:

样例中的矩形

需要计算的周长为蓝色图案的所有边缘:

需要计算的周长

对于 5 分的数据, n\leq 10

对于 15 分的数据, n \leq 100

对于 25 分的数据, n \leq 5000

登录以提交代码。
单点时限 2 秒
内存限制 256 MB
提交 2
通过 2