问题2697--海报(picture)

2697: 海报(picture)

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 4
[提交] [状态] [讨论版] [命题人:]

题目描述

墙上粘贴了n个相同形状的矩形海报。
它们的边都是垂直或水平的。
每个矩形可以被其他矩形部分或完全覆盖。
所有矩形的并集边界的长度称为周长。
现在请你编程计算这个周长是多少。
图1显示了一个包含7个矩形的图形样例:


图2给出了它的并集边界:


每个矩形的顶点都有一个整数坐标。

输入

第一行输入整数n,表示矩形的数量。
接下来n行,每行四个整数x1,y1,x2,y2用以描述一个矩形,(x1,y1)为矩形的左下角坐标,(x2,y2)为矩形的右上角坐标。
0≤n<5000,  −10000≤xi,yi≤10000

输出

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

样例输入 Copy

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

样例输出 Copy

228

来源/分类