3323 - 矩形周长并

在平面上有很多矩形,可以重叠,它们的边都平行于坐标轴。求所有矩形的并集的边界的长度。

输入

输入:有多个测试用例,以输入0为结束标记。对于每个用例,第一行是整数n,表示矩形数量,后面有n行,每一行用4个整数表示一个矩形的左下角和右上角坐标。n<5000,坐标值范围[-10000,10000],矩形面积都是正的。

输出

输出每个用例的矩形并的周长。

样例

输入

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
0

输出

228
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题