企业官网建设流程全解析

P1034 矩形覆盖

网页链接

P1034 矩形覆盖

题目描述

在平面上有n nn个点，每个点用一对整数坐标表示。例如：当n = 4 n=4n=4时，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 k=2k=2时，可用如图二的两个矩形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 i+1i+1行有两个整数x i , y i x_i,y_ixi​,yi​，表示平面上第i ii个点的坐标。

输出格式

共一行一个整数，为满足条件的最小的矩形面积之和。

输入输出样例 #1

输入 #1

4 2 1 1 2 2 3 6 0 7

输出 #1

4

说明/提示

对于100 % 100\%100%数据，满足1 ≤ n ≤ 50 1\le n \le 501≤n≤50，1 ≤ k ≤ 4 1 \le k \le 41≤k≤4，0 ≤ 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≤50，k ≤ 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 + 剪枝）

1. 数据结构：
   • 点结构体P{x, y}，存储所有点。
   • 矩形结构体R{x1, y1, x2, y2}，初始时x1=y1=501，x2=y2=-1，表示空矩形。
2. 面积计算：ar(R)返回矩形面积，若矩形为空（x1 > x2或y1 > y2）则返回 0。
3. 重叠判断：ov(R a, R b)检查两个非空矩形是否重叠。若在横轴或纵轴上完全分离（a.x2 < b.x1 || b.x2 < a.x1 || a.y2 < b.y1 || b.y2 < a.y1）则返回false，否则返回true（重叠）。注意使用严格小于，保证边界接触也算重叠。
4. 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≤i<k）：
     • 如果第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。
5. 初始化：res设为一个极大值（如1e9），从dfs(1, 0)开始搜索。
6. 输出：res即为最小面积和。

3. 复杂度分析

• 搜索空间：每个点有k kk种分配，最坏k n k^nkn。但k ≤ 4 k \le 4k≤4，n ≤ 50 n \le 50n≤50，且通过矩形重叠检查和面积和剪枝，实际搜索状态远小于理论上限。
• 每次操作：更新矩形、检查重叠需要O ( k ) O(k)O(k)时间，k ≤ 4 k \le 4k≤4。
• 总体复杂度：在题目数据范围内（n ≤ 50 n \le 50n≤50，k ≤ 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。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;structP{ll x,y;}p[55];structR{ll x1,x2,y1,y2;R(){x1=y1=501;x2=y2=-1;}};ll n,k,res=1e9;R r[5];llar(R a){if(a.x1>a.x2||a.y1>a.y2)return0;return(a.x2-a.x1)*(a.y2-a.y1);}boolov(R a,R b){if(a.x1>a.x2||a.y1>a.y2||b.x1>b.x2||b.y1>b.y2)returnfalse;if(a.x2<b.x1||b.x2<a.x1||a.y2<b.y1||b.y2<a.y1)returnfalse;returntrue;}voiddfs(ll id,ll s){if(s>=res)return;if(id>n){res=min(res,s);return;}for(ll i=0;i<k;i++){if(r[i].x1>r[i].x2){boolhe=false;for(ll j=0;j<i;j++)if(r[j].x1>r[j].x2){he=true;break;}if(he)continue;}R 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);boolf=true;for(ll j=0;j<k;j++)if(i!=j&&ov(r[i],r[j])){f=false;break;}if(f)dfs(id+1,s+ar(r[i])-ar(t));r[i]=t;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>k;for(ll i=1;i<=n;i++)cin>>p[i].x>>p[i].y;dfs(1,0);cout<<res<<endl;return0;}