83454 - Terytoria
时间限制 : 4 秒
内存限制 : 256 MB
在二维平面直角坐标系上,有一个长度为 X,宽度为 Y 的地图,注意这个地图的左边界和右边界是连通的,下边界和上边界也是连通的。
在这个地图里,有 X\times Y 个格子以及 n 个边平行坐标轴的矩形。你只知道每个矩形两个对顶点的坐标,请问在最好情况下,被所有 n 个矩形都覆盖住的格子数量有多少?
输入
第一行三个正整数 n,X,Y。
接下来 n 行,每行四个整数 x_1,y_1,x_2,y_2(0\le x_1,x_2 < X,0\le y_1,y_2 < Y,x_1\ne x_2,y_1\ne y_2),表示第 i 个矩形两个对顶点的坐标为 (x_1,y_1) 和 (x_2,y_2)。
输出
输出一行一个整数,即被所有 n 个矩形都覆盖住的格子数量的最大可能值。
样例
输入
2 10 7 2 1 8 6 5 2 4 4
输出
15
提示
对于 100\% 的数据,1\le n\le 5\times 10^5,2\le X,Y\le 10^9。
来源
PA