问题 C: 火星探险(矩形覆盖问题)

问题 C: 火星探险(矩形覆盖问题)

时间限制: 1 Sec  内存限制: 256 MB
提交: 11  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

在2051年,若干火星探险队探索了这颗红色行星的不同的区域并且制作了这些区域的地图。现在, Baltic空间机构有一个雄心勃勃的计划:他们想制作一张整个行星的地图。为了考虑必要的工作,他们需要知道地图上已经存在的全部区域的大小。你的任务是写一个计算这个区域大小的程序。
具体任务要求为:
(l)从输入文件mars.in读取地图形状的描述;
(2)计算地图覆盖的全部的区域;
(3)输出到文件mars.out中。


输入

输入第一行包含一个整数N(1N10000),表示可得到的地图数目。
以下N行,每行描述一张地图。
每行包含4个整数x1,y1,x2和y2(0≤x1<x2≤30000,0≤y1<y2≤30 000)。数值(x1,y1)和(x2,y2)是坐标,分别表示绘制区域的左上角和右下角坐标。每张地图是矩形的,并且它的边是平行与X坐标轴或Y坐标轴的。


输出

输出应该包含一个整数,表示探索区域的总面积(即所有矩形的公共面积)。

样例输入 Copy

2
10 10 20 20
15 15 25 30

样例输出 Copy

225