Aizu - 0531 Paint Color（离散化+imos） - MeloのblogMeloのblog
为了宣传信息竞赛，要在长方形的三合板上喷油漆来制作招牌。三合板上不需要涂色的部分预先贴好了护板。被护板隔开的区域要涂上不同的颜色，比如上图就应该涂上5种颜色。
请编写一个程序计算涂色数量，输入数据中，保证看板不会被护板全部遮住，并且护板的边一定是水平或垂直的。
输入：
第一个数是宽w（1 ≤ w ≤ 1000000），第二个数是高h（1 ≤ h ≤ 1000000）。
第二行是护板的数量n（1 ≤ n ≤ 1000），接着n行是每个护板的左下角坐标 (x1 , y1 )和右上角坐标 (x2 , y2 )，用空格隔开： x1 , y1 , x2 , y2 (0 ≤ x1< x2 ≤ w, 0 ≤ y1 < y2 ≤ h 都是整数)
招牌的坐标系如下，左下角是 (0, 0) ，右上角是(w, h) ， 测试集中的30%都满足w ≤ 100, h ≤ 100, n ≤ 100。
题解：
由于N远远小于w和h，所以我们对坐标进行离散化处理。离散化的话，没有什么好说的，需要注意的是这里的给出的是坐标左下角(x1,y1)和右上角(x2,y2)，即对应的方格区域应该是左闭右开的。
这里推荐一下imos算法，可以高效的计算多维空间里重复矩阵的面积。
这里给甩出一个链接，解释的挺好的。传送BiuBiu~
Read full article from Aizu - 0531 Paint Color（离散化+imos） - MeloのblogMeloのblog
No comments:
Post a Comment