P83323

矩形周长并

难度 未定 初三 线段树 扫描线
讨论 统计 8通过 22提交 36.4%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

输入

输入:有多个测试用例,以输入0为结束标记。对于每个用例,第一行是整数n,表示矩形数量,后面有n行,每一行用4个整数表示一个矩形的左下角和右上角坐标。n<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
0
输出
228
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交