1467. Mars Maps

单点时限: 2.0 sec

内存限制: 256 MB

In the year 2051, several Mars expeditions have explored different areas of the red planet and produced maps of these areas. Now, the BaSA (Baltic Space Agency) has an ambitious plan: they would like to produce a map of the whole planet. In order to calculate the necessary effort, they need to know the total size of the area for which maps already exist. It is your task to write a program that calculates this area.

Write a program that:

reads the description of map shapes,

computes the total area covered by the maps,

writes the result.

输入格式

The inputstarts with a line containing a single integer N (1<=N<=10 000), the number of available maps. Each of the following N lines describes a map. Each of these lines contains four integers x1, y1, x2 and y2 (0<=x1<x2<=30 000, 0<=y1<y2<=30 000). The values (x1,y1) and (x2,y2) are the coordinates of, respectively, the bottom-left and the top-right corner of the mapped area. Each map has rectangular shape, and its sides are parallel to the x- and y-axis of the coordinate system.

输出格式

The output should contain one integer A, the total explored area (i.e. the area of the union of all rectangles).

样例

Input
2
10 10 20 20
15 15 25 30
Output
225

11 人解决,19 人已尝试。

17 份提交通过,共有 77 份提交。

6.5 EMB 奖励。

创建: 17 年,2 月前.

修改: 7 年,1 月前.

最后提交: 1 年,3 月前.

来源: BOI 2001

题目标签