#263. 形成的区域

形成的区域

题目描述

nn 个不同颜色且不透明的长方形被放在一张宽为 aa 长为 bb 的白纸上。它们的边于白纸的边缘平行,且所有的长方形都放置在白纸内。

现在将他们重叠,重叠后会出现不同形状的各种颜色,你需要求出每种颜色的面积。

白纸的左下角的坐标为原点 (0,0)(0,0),且坐标轴平行于白纸边缘。

输入格式

输入数据共 n+1n+1 行。

第一行三个整数,a,b,na,b,n

第二到 n+1n+1 行,每行五个整数,llx,lly,urx,ury,colorllx,lly,urx,ury,color,表示一个长方形的左下角和右上角的坐标以及颜色编号。注:颜色 1 和底部白纸的颜色相同

输出格式

一个所有能被看到颜色和该颜色的总面积的汇总,一行内格式为编号和面积,即使颜色的区域不是连续的,仍可以输出,并且按 colorcolor 的增序排序输出,不要输出没有区域的颜色。

20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
1 91
2 84
3 187
4 38

提示

白纸经过各层覆盖后,各种颜色的面积分别为 91,84,187,3891,84,187,38

数据范围

对于 100%100\% 的数据,1n1031 \leq n \leq 10^31a,b1041 \leq a,b \leq 10^41llx,lly,urx,urya,b1 \leq llx,lly,urx,ury \leq a,b1colorn+11 \leq color \leq n+1