9008: 洛谷P5490 -【模板题】扫描线
[Creator : ]
Description
求 $n$ 个四边平行于坐标轴的矩形的面积并。
Input
第一行一个正整数 $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$ 行每行四个非负整数 $x_1, y_1, x_2, y_2$，表示一个矩形的四个端点坐标为 $(x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)$。
Output
一行一个正整数，表示 $n$ 个矩形的并集覆盖的总面积。
Constraints
对于 $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$。
对于 $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$。
Sample 1 Input
2
100 100 200 200
150 150 250 255
Sample 1 Output
18000
