#570. 田地丈量
田地丈量
问题描述
西西艾弗岛上散落着 块田地。每块田地可视为平面直角坐标系下的一个矩形区域,由左下角坐标 和右上角坐标 唯一确定,并满足 。
已知这 块田地两两的内部互不相交(交集面积为 ,可能在边界处接触或重合)。
顿顿想在区域 (左下角 ,右上角 )开垦一块矩形田地。请计算顿顿选定区域内已经存在的田地面积总和(即所有已存在田地与该区域的交集面积之和)。
输入格式
共 行:
第一行包含三个正整数 ,分别表示田地块数以及选定矩形的右上角坐标。
接下来 行,每行包含四个整数 ,表示一块田地的左下与右上坐标。
- 。
- 所有输入坐标的绝对值均不超过 。
- 矩形保证 且 。
- 任意两块田地的 内部 交集面积为 。
输出格式
输出一行,包含一个整数,表示顿顿选定区域内已存在的田地面积总和。
输入样例
4 10 10
0 0 5 5
5 -2 15 3
8 8 15 15
-2 10 3 15
输出样例
44
说明
样例解释
对每块田地分别求与选定区域 的重叠面积并累加,结果为 。
