3793 - 【模板】扫描线
描述

求 n 个四边平行于坐标轴的矩形的面积并。

输入

第一行一个正整数 n。

接下来 n 行每行四个非负整数 x_1, y_1, x_2, y_2,表示一个矩形的四个端点坐标为 (x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)。

输出

一行一个正整数,表示 n 个矩形的并集覆盖的总面积。

样例

输入

2
100 100 200 200
150 150 250 255

输出

18000
提示

对于 20\% 的数据,1 \le n \le 1000。
对于 100\% 的数据,1 \le n \le {10}^5,0 \le x_1 < x_2 \le {10}^9,0 \le y_1 < y_2 \le {10}^9。

Updated on 4.10 by Dengduck(口胡) \& yummy(实现):增加了一组数据。

来源
洛谷 P5490 【模板】扫描线 & 矩形面积并
标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 1
通过次数 1