#P1177. Picture

Picture

题目描述

若干形状相同的矩形海报、照片和其他图片被贴在墙上。它们的边都是垂直或水平的。每个矩形可能被其他矩形部分或完全覆盖。所有矩形并集的边界长度称为周长。

请编写程序计算该周长。图1展示了一个包含7个矩形的示例,对应的边界如图2中所有线段所示。所有矩形的顶点坐标均为整数。

输入

程序从标准输入读取数据。第一行包含贴在墙上的矩形数量。接下来每行包含一个矩形的左下角顶点和右上角顶点的整数坐标,坐标对以x坐标 y坐标的形式给出。

  • 矩形数量满足 (0 \leq \text{数量} < 5000)
  • 所有坐标取值范围为 ([-10000, 10000]),且每个矩形的面积为正(即左下角坐标严格小于右上角坐标)。

输出

程序向标准输出写入一行,包含一个非负整数,表示输入矩形并集的周长。

输入数据 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  

输出数据 1

228