#3924. 平面覆盖
平面覆盖
问题描述:
在一个二维平面上,有 n 个矩形,每个矩形的边缘与坐标轴平行,且由其左下角和右上角的坐标 (x1, y1) 和 (x2, y2) 表示。你需要选择若干个不重叠的矩形,使得选择的矩形的面积之和最大。不同于普通的区域不相交问题,这里要求每个矩形的面积都是正数,且每次选择的矩形的边界必须完全不重叠。
重叠定义: 如果两个矩形的任何部分相交(包括边界),则认为它们重叠;如果完全不相交,则认为它们不重叠。
输入:
第一行包含一个整数 n,表示矩形的数量(1 ≤ n ≤ 1000)。 接下来的 n 行,每行包含四个整数 x1, y1, x2, y2,表示矩形的左下角坐标 (x1, y1) 和右上角坐标 (x2, y2)(0 ≤ x1 < x2 ≤ 1000,0 ≤ y1 < y2 ≤ 1000)。
输出:
输出选择的最大不重叠矩形的总面积。
输入样例:
5
1 1 3 3
2 2 4 4
3 1 5 3
6 6 8 8
4 4 6 6
输出样例:
12
解释:
对于输入示例中的矩形,最优的选择是:
选择矩形 (1, 1, 3, 3) 和 (6, 6, 8, 8),它们不重叠,面积分别是 4 和 4。 选择矩形 (3, 1, 5, 3),面积为 4。 因此,最大面积和为 4 + 4 + 4 = 12。