P1034 矩形覆盖【洛谷算法习题】

P1034 矩形覆盖网页链接P1034 矩形覆盖题目描述在平面上有n nn个点每个点用一对整数坐标表示。例如当n 4 n4n4时4 44个点的坐标分别为p 1 ( 1 , 1 ) p_1(1,1)p1​(1,1)p 2 ( 2 , 2 ) p_2(2,2)p2​(2,2)p 3 ( 3 , 6 ) p_3(3,6)p3​(3,6)p 4 ( 0 , 7 ) p_4(0,7)p4​(0,7)见图一。这些点可以用k kk个矩形全部覆盖矩形的边平行于坐标轴。当k 2 k2k2时可用如图二的两个矩形s 1 , s 2 s_1,s_2s1​,s2​覆盖s 1 , s 2 s_1,s_2s1​,s2​面积和为4 44。问题是当n nn个点坐标和k kk给出后怎样才能使得覆盖所有点的k kk个矩形的面积之和为最小呢约定覆盖一个点的矩形面积为0 00覆盖平行于坐标轴直线上点的矩形面积也为0 00。各个矩形必须完全分开边线与顶点也都不能重合。输入格式第一行共两个整数n , k n,kn,k含义如题面所示。接下来n nn行其中第i 1 i1i1行有两个整数x i , y i x_i,y_ixi​,yi​表示平面上第i ii个点的坐标。输出格式共一行一个整数为满足条件的最小的矩形面积之和。输入输出样例 #1输入 #14 2 1 1 2 2 3 6 0 7输出 #14说明/提示对于100 % 100\%100%数据满足1 ≤ n ≤ 50 1\le n \le 501≤n≤501 ≤ k ≤ 4 1 \le k \le 41≤k≤40 ≤ x i , y i ≤ 500 0 \le x_i,y_i \le 5000≤xi​,yi​≤500。【题目来源】NOIP 2002 提高组第四题解题思路本题是搜索 剪枝的经典问题。给定平面上n nn个点要求用k kk个边平行于坐标轴的矩形完全覆盖所有点且任意两个矩形不能有公共点包括边界和顶点求所有矩形面积之和的最小值。由于n ≤ 50 n \le 50n≤50k ≤ 4 k \le 4k≤4可以采用深度优先搜索依次将每个点分配到k kk个矩形之一同时维护每个矩形当前的边界并实时检查矩形之间是否重叠。通过面积和剪枝可以高效找到最优解。1. 问题等价转化每个点必须属于且仅属于一个矩形。矩形的边界由其所包含的点的最小/最大横纵坐标决定面积为( x max ⁡ − x min ⁡ ) × ( y max ⁡ − y min ⁡ ) (x_{\max}-x_{\min}) \times (y_{\max}-y_{\min})(xmax​−xmin​)×(ymax​−ymin​)。要求任意两个矩形完全分离即不能有重叠部分也不能有边界或顶点接触。判断条件为两个矩形在横轴和纵轴上的投影都不相交严格不相交即一个矩形的右边界必须小于另一个矩形的左边界或上边界小于下边界等。目标最小化k kk个矩形面积之和。2. 算法实现DFS 剪枝数据结构点结构体P{x, y}存储所有点。矩形结构体R{x1, y1, x2, y2}初始时x1y1501x2y2-1表示空矩形。面积计算ar(R)返回矩形面积若矩形为空x1 x2或y1 y2则返回 0。重叠判断ov(R a, R b)检查两个非空矩形是否重叠。若在横轴或纵轴上完全分离a.x2 b.x1 || b.x2 a.x1 || a.y2 b.y1 || b.y2 a.y1则返回false否则返回true重叠。注意使用严格小于保证边界接触也算重叠。DFS 过程dfs(id, s)id表示当前处理到第几个点s表示当前已累加的面积和。剪枝若s res当前最优解直接返回。终止条件若id n更新res min(res, s)返回。对于当前点p[id]尝试放入第i ii个矩形0 ≤ i k 0 \le i k0≤ik如果第i ii个矩形为空r[i].x1 r[i].x2则检查前面是否已有空矩形j i且r[j]为空。若有则跳过避免因矩形顺序不同而重复搜索同一分配方案。备份原矩形t r[i]更新矩形边界包含当前点r[i].x1 min(r[i].x1, p[id].x); r[i].x2 max(r[i].x2, p[id].x); r[i].y1 min(r[i].y1, p[id].y); r[i].y2 max(r[i].y2, p[id].y);检查更新后的第i ii个矩形是否与其他所有非空矩形重叠。若重叠则放弃该分配恢复矩形r[i] t并尝试下一个矩形。若不重叠则递归调用dfs(id 1, s ar(r[i]) - ar(t))其中面积增量是加入当前点后矩形面积的增加量。回溯时恢复矩形r[i] t。初始化res设为一个极大值如1e9从dfs(1, 0)开始搜索。输出res即为最小面积和。3. 复杂度分析搜索空间每个点有k kk种分配最坏k n k^nkn。但k ≤ 4 k \le 4k≤4n ≤ 50 n \le 50n≤50且通过矩形重叠检查和面积和剪枝实际搜索状态远小于理论上限。每次操作更新矩形、检查重叠需要O ( k ) O(k)O(k)时间k ≤ 4 k \le 4k≤4。总体复杂度在题目数据范围内n ≤ 50 n \le 50n≤50k ≤ 4 k \le 4k≤4可以快速通过。总结本题通过 DFS 枚举点的矩形归属实时维护每个矩形的边界并检查矩形间是否严格分离。利用“空矩形只从第一个开始使用”避免重复搜索并利用当前面积和与已知最优解的剪枝大幅减少搜索量。算法思路直观适合小规模数据。代码简要说明结构体P与R分别存储点和矩形。函数ar(R)计算矩形面积空矩形返回 0。函数ov(R, R)判断两个矩形是否重叠包括边界接触。函数dfs(id, s)id为当前点编号s为当前面积和。剪枝s res时返回。遍历k kk个矩形若矩形为空且前面已有空矩形则跳过。尝试将当前点加入第i ii个矩形更新边界后检查是否与其他矩形重叠。若不重叠递归处理下一个点并累加面积增量。回溯恢复矩形状态。主函数读入n , k n, kn,k和点坐标初始化res调用dfs(1, 0)输出res。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structP{ll x,y;}p[55];structR{ll x1,x2,y1,y2;R(){x1y1501;x2y2-1;}};ll n,k,res1e9;R r[5];llar(R a){if(a.x1a.x2||a.y1a.y2)return0;return(a.x2-a.x1)*(a.y2-a.y1);}boolov(R a,R b){if(a.x1a.x2||a.y1a.y2||b.x1b.x2||b.y1b.y2)returnfalse;if(a.x2b.x1||b.x2a.x1||a.y2b.y1||b.y2a.y1)returnfalse;returntrue;}voiddfs(ll id,ll s){if(sres)return;if(idn){resmin(res,s);return;}for(ll i0;ik;i){if(r[i].x1r[i].x2){boolhefalse;for(ll j0;ji;j)if(r[j].x1r[j].x2){hetrue;break;}if(he)continue;}R tr[i];r[i].x1min(r[i].x1,p[id].x);r[i].x2max(r[i].x2,p[id].x);r[i].y1min(r[i].y1,p[id].y);r[i].y2max(r[i].y2,p[id].y);boolftrue;for(ll j0;jk;j)if(i!jov(r[i],r[j])){ffalse;break;}if(f)dfs(id1,sar(r[i])-ar(t));r[i]t;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnk;for(ll i1;in;i)cinp[i].xp[i].y;dfs(1,0);coutresendl;return0;}