#570. 田地丈量

    ID: 570 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 2 上传者: 标签>CCF CSP认证第 29 次CCF CSP软件能力认证基础算法模拟

田地丈量

问题描述

西西艾弗岛上散落着 nn 块田地。每块田地可视为平面直角坐标系下的一个矩形区域,由左下角坐标 (x1,y1)(x_1,y_1) 和右上角坐标 (x2,y2)(x_2,y_2) 唯一确定,并满足 x1<x2,  y1<y2x_1<x_2,\;y_1<y_2

已知这 nn 块田地两两的内部互不相交(交集面积为 00,可能在边界处接触或重合)。

顿顿想在区域 [0,a]×[0,b][0,a]\times[0,b](左下角 (0,0)(0,0),右上角 (a,b)(a,b))开垦一块矩形田地。请计算顿顿选定区域内已经存在的田地面积总和(即所有已存在田地与该区域的交集面积之和)。

输入格式

n+1n+1 行:

第一行包含三个正整数 n,a,bn,a,b,分别表示田地块数以及选定矩形的右上角坐标。

接下来 nn 行,每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示一块田地的左下与右上坐标。

  • n100n \le 100
  • 所有输入坐标的绝对值均不超过 10410^4
  • 矩形保证 x1<x2x_1<x_2y1<y2y_1<y_2
  • 任意两块田地的 内部 交集面积为 00

输出格式

输出一行,包含一个整数,表示顿顿选定区域内已存在的田地面积总和。

输入样例

4 10 10
0 0 5 5
5 -2 15 3
8 8 15 15
-2 10 3 15

输出样例

44

说明

样例解释

对每块田地分别求与选定区域 [0,10]×[0,10][0,10]\times[0,10] 的重叠面积并累加,结果为 4444