BZPRO
#5553. [PA2019]Terytoria
内存限制：256 MiB
时间限制：60 Sec
提交
提交记录
讨论
题目描述
在二维平面直角坐标系上，有一个长度为X，宽度为Y的地图，注意这个地图的左边界和右边界是连通的，下边界和上边界也是连通的，换言之它是个球形结构。
在这个地图里，有X*Y个格子以及n个边平行坐标轴的矩形。你只知道每个矩形两个对顶点的坐标，请问在最好情况下，被所有n个矩形都覆盖住的格子数量有多少？
输入格式
第一行三个正整数n,X,Y(1<=n<=500000,2<=X,Y<=10^9)。
接下来n行，每行四个整数x_1,y_1,x_2,y_2(0<=x_1,x_2<X,0<=y_1,y_2<Y,x_1!=x_2,y_1!=y_2)，表示第i个矩形两个对顶点的坐标为(x_1,y_1)和(x_2,y_2)。
输出格式
输出一行一个整数，即被所有n个矩形都覆盖住的格子数量的最大可能值。
样例
样例输入
2 10 7
2 1 8 6
5 2 4 4
样例输出
15
数据范围与提示
下图列举了一些情况，其中第3种情况是最优的。
BZPRO.png)