洛谷P1034 矩形覆盖

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[5];
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=1;j<cnt;j++){
            if(be[cnt].x1==be[j].x2&&be[cnt].y1<=be[j].y2)return;
        }
        dfs(i+1,cnt+1,sum+(be[cnt].x2-be[cnt].x1)*(be[cnt].y2-be[cnt].y1));
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].y,&a[i].x);
    sort(a+1,a+n+1);
    dfs(1,1,0);
    printf("%d",ans);
}