记录编号	590031	评测结果	AWWWTTW
题目名称	[NOIP 2002]矩形覆盖	最终得分	14
用户昵称	Untitled	是否通过	未通过
代码语言	C++	运行时间	2.251 s
提交时间	2024-07-09 14:24:46	内存使用	3.28 MiB

#include <bits/stdc++.h>
using namespace std;

int const INF=600;
int n,k,res=INT_MAX,x[60],y[60];
bool d[60];
struct node{
    int x1,y1,x2,y2;
} sq[10];

int sg(){
    int cnt=0;
    //cout<<sq[1].x1<<' '<<sq[1].y1<<' '<<sq[1].x2<<' '<<sq[1].y2<<' '<<sq[2].x1<<' '<<sq[2].y1<<' '<<sq[2].x2<<' '<<sq[2].y2<<'\n';
    for (int i=1;i<=k;i++){
        if (sq[i].x1>500 || sq[i].x2==-1) return -1;
        for (int j=1;j<=k;j++){
            if (i==j) continue;
            if (sq[i].x2>=sq[j].x1 && sq[i].y2<=sq[j].y1 && sq[i].x1<=sq[j].x2 && sq[i].y1>=sq[j].y2) return -1;
            if (sq[i].x2>=sq[j].x1 && sq[i].y2>=sq[j].y1 && sq[i].x1<=sq[j].x2 && sq[i].y1<=sq[j].y2) return -1;
        }
        cnt+=abs(sq[i].x2-sq[i].x1)*abs(sq[i].y1-sq[i].y2);
    }
    return cnt;
}

void dfs(int t){
    if (t>n){
        int cnt=sg();
        if (cnt>=0){
            res=min(res,cnt);
            //cout<<sq[1].x1<<' '<<sq[1].y1<<' '<<sq[1].x2<<' '<<sq[1].y2<<' '<<sq[2].x1<<' '<<sq[2].y1<<' '<<sq[2].x2<<' '<<sq[2].y2<<'\n';
        }
        return;
    }
    int lx1,ly1,lx2,ly2;
    for (int i=1;i<=k;i++){
        lx1=sq[i].x1,lx2=sq[i].y1,ly1=sq[i].x2,ly2=sq[i].y2;
        sq[i].x1=min(sq[i].x1,x[t]);
        sq[i].y1=max(sq[i].y1,y[t]);
        sq[i].x2=max(sq[i].x2,x[t]);
        sq[i].y2=min(sq[i].y2,y[t]);
        dfs(t+1);
        sq[i].x1=lx1,sq[i].y1=ly1,sq[i].x2=lx2,sq[i].y2=ly2;
    }
    return;
}

int main(){
    freopen("jxfg.in","r",stdin);
    freopen("jxfg.out","w",stdout);
    
    scanf("%d %d",&n,&k);
    for (int i=1;i<=n;i++){
        scanf("%d %d",&x[i],&y[i]);
    }
    for (int i=1;i<=k;i++) sq[i].x1=INF,sq[i].x2=-1,sq[i].y1=-1,sq[i].y2=INF;
    dfs(1);
    printf("%d",res);
    
    return 0;
}