#P1884. [USACO12FEB] Overplanting S

[USACO12FEB] Overplanting S

题目描述

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.

在一个笛卡尔平面坐标系里(则X轴向右是正方向,Y轴向上是正方向),有N(1<=N<=10001<=N<=1000)个矩形,第i个矩形的左上角坐标是(x1, y1),右下角坐标是(x2,y2)。问这N个矩形所覆盖的面积是多少?注意:被重复覆盖的区域的面积只算一次。

输入格式

第一行,一个整数N。 (1<=N<=10001<=N<=1000)。

接下来有N行,每行描述一个矩形的信息,分别是矩形的x1、y1、x2、y2。

其中 108<=x1,y1,x2,y2<=108-10^8<=x1,y1,x2,y2<=10^8

输出格式

一个整数,被N个矩形覆盖的区域的面积。

2
0 5 4 1
2 4 6 2
20