链接: https://cses.fi/problemset/task/1741

板块: Geometry

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定 $n$ 个矩形，你的任务是求出它们并集的总面积。

输入

第一行包含一个整数 $n$：矩形的数量。

接下来有 $n$ 行描述这些矩形。每行包含四个整数 $x_1$、$y_1$、$x_2$ 和 $y_2$：一个矩形从点 $(x_1,y_1)$ 开始，到点 $(x_2,y_2)$ 结束。

输出

输出这些矩形所覆盖的总面积。

数据范围

$1 \le n \le 10^5$ $-10^6 \le x_1 < x_2 \le 10^6$ $-10^6 \le y_1 < y_2 \le 10^6$

样例输入

3
1 3 4 5
3 1 7 4
5 3 8 6

样例输出

24