洛谷P1034 矩形覆盖
2024-08-25 22:38:22
P1034 矩形覆盖
题目描述
在平面上有 n 个点(n <= 50),每个点用一对整数坐标表示。例如:当 n=4 时,4个点的坐标分另为:p1(1,1),p2(2,2),p3(3,6),P4(0,7),见图一。
这些点可以用 k 个矩形(1<=k<=4)全部覆盖,矩形的边平行于坐标轴。当 k=2 时,可用如图二的两个矩形 sl,s2 覆盖,s1,s2 面积和为 4。问题是当 n 个点坐标和 k 给出后,怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定:覆盖一个点的矩形面积为 0;覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开(边线与顶点也都不能重合)。
输入输出格式
输入格式:
n k xl y1 x2 y2 ... ...
xn yn (0<=xi,yi<=500)
输出格式:
输出至屏幕。格式为:
一个整数,即满足条件的最小的矩形面积之和。
输入输出样例
输入样例#1:
4 2
1 1
2 2
3 6
0 7
输出样例#1:
4
说一下如何判断两矩形重叠
因为我们把所有点按照x递增,y递增的顺序排序,所以下一个矩形与当前矩形只有可能有一条边重合,如上图所示,当前矩形的下边界一定在上个矩形下边界上边,只要保证这个下边界也在上个矩形上边界的下边就可以确定两个矩形重合了
#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 52
using namespace std;
int n,k,ans=0x7fffffff;
struct node{
int x,y;
bool operator < (const node b)const{
if(x==b.x)return y<b.y;
return x<b.x;
}
}a[maxn];
struct Node{
int x1,y1,x2,y2;
}be[];
void dfs(int pos,int cnt,int sum){
if(sum>=ans)return;
if(pos>n){
ans=min(ans,sum);
return;
}
if(cnt>k)return;
be[cnt].x1=be[cnt].x2=a[pos].x;
be[cnt].y1=be[cnt].y2=a[pos].y;
for(int i=pos;i<=n;i++){
be[cnt].x1=min(be[cnt].x1,a[i].x);
be[cnt].y1=min(be[cnt].y1,a[i].y);
be[cnt].x2=max(be[cnt].x2,a[i].x);
be[cnt].y2=max(be[cnt].y2,a[i].y);
for(int j=;j<cnt;j++){
if(be[cnt].x1==be[j].x2&&be[cnt].y1<=be[j].y2)return;
}
dfs(i+,cnt+,sum+(be[cnt].x2-be[cnt].x1)*(be[cnt].y2-be[cnt].y1));
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)scanf("%d%d",&a[i].y,&a[i].x);
sort(a+,a+n+);
dfs(,,);
printf("%d",ans);
}
最新文章
- TaintDroid剖析之DVM变量级污点跟踪(下篇)
- iOS UITableViewController出现crash
- ubuntu14安装Qt
- 第二十四篇:导出SOUI对象到LUA脚本
- 瞧,这就是UE4 C++
- 一个统计目录文件大小的php函数
- java web-----MVC设计模式
- HW2.4
- Qt标准对话框之QColorDialog
- dos插入mysql乱码
- FreeMarker 快速入门
- 敏捷冲刺每日报告二(Java-Team)
- VMware 12 安装 Windows server 2008 系统
- eclipse 带sts插件
- 学c++需要先学c语言吗?
- [20170622]传输表空间与dblink.txt
- bzoj3876: [Ahoi2014&;Jsoi2014]支线剧情
- flask 入门(二)
- 深入理解yield(二):yield与协程
- [label][翻译][JavaScript Regular Expression]JavaScript Regular Expressions