8425: Overplanting (Silver)

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:3 通过:1

题目描述

Problem 1: Overplanting (Silver) [Brian Dean, 2012] Farmer John has purchased a new machine that is capable of planting grass within any rectangular region of his farm that is "axially aligned" (i.e., with vertical and horizontal sides). Unfortunately, the machine malfunctions one day and plants grass in not one, but N (1 <= N <= 1000) different rectangular regions, some of which may even overlap. Given the rectangular regions planted with grass, please help FJ compute the total area in his farm that is now covered with grass.


农夫约翰购买了一台新机器,该机器能够在其农场的任何“轴向对齐”(即具有垂直和水平边)的矩形区域内种草。

不幸的是,这台机器有一天出了故障,并在 N 个不同的矩形区域内进行了种草工作,其中一些区域可能会有重叠。

给定机器工作的具体 N 个矩形区域,请你计算种上草的区域的总面积是多少。


输入格式

* Line 1: The integer N.

第一行包含整数 N。

接下来 N 行,每行包含四个整数 x1,y1,x2,y2,表示其中一个矩形区域的左上角坐标 (x1,y1)和右下角坐标 (x2,y2)

输出格式

* Lines 2..1+N: Each line contains four space-separated integers x1 y1 x2 y2 specifying a rectangular region with upper-left corner (x1,y1) and lower-right corner (x2,y2). All coordinates are in the range -10^8...10^8.

输出种上草的区域的总面积。


输入样例 复制

2
0 5 4 1
2 4 6 2

输出样例 复制

20

数据范围与提示

1≤N≤10001≤N≤1000,
−108≤x1,y1,x2,y2≤108