题目描述

求 $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

2
100 100 200 200
150 150 250 255

18000

21
8651 6894 9699 9900
9068 8113 10102 8408
3761 1134 10667 4602
4079 2861 10466 6900
98 9279 1042 9814
1496 9790 3448 10119
7019 9982 7560 10532
9877 9945 10049 10321
1943 3775 7526 4285
7464 3790 7971 4101
1720 9531 9247 10884
1687 2098 5386 8740
3986 7704 5389 8244
5152 8450 6455 9910
8991 3526 9770 6255
3736 3352 9680 10659
4269 3640 7802 5127
2408 552 9628 5919
3754 3923 5256 7532
2507 5024 5616 9962
6626 8342 8656 9960

86696489

22
4218 2660 7389 4777
4811 5902 6684 6933
5413 647 10386 9367
7814 931 8401 10090
3905 2561 4862 10884
6105 186 8511 2118
4110 7216 4436 10439
1489 6248 3284 6932
8711 5830 10221 10360
8160 2131 8614 7315
768 2289 9119 9220
1196 8799 3673 9789
7202 8005 7624 10857
8932 1722 10805 3540
8908 4056 9553 6537
851 9514 3863 9566
6439 8171 8669 10681
6054 885 9170 1855
8573 5171 10689 9873
5738 536 9567 4122
3111 1067 8557 9818
9350 5831 10650 8008

90401389

提示

对于 $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（实现）：增加了一组数据。