记录编号	331287	评测结果	AAAAAWA
题目名称	[NOIP 2002]矩形覆盖	最终得分	85
用户昵称	KZNS	是否通过	未通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-10-27 16:43:26	内存使用	0.29 MiB

//KZNS
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 53
int N, K;
int ls[Nmax][2];
int ans = 0x7fffffff;
void init() {
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++)
        scanf("%d %d", &ls[i][0], &ls[i][1]);
}
bool ud[4];
int blk[4][4];//wasd
int aaa[4][4];
void DFS(int id) {
    int u = 0;
    if (id >= N) {
        for (int i = 0; i < K; i++)
            if (ud[i])
                u += (blk[i][0] - blk[i][2]) * (blk[i][3] - blk[i][1]);
            else
                return;
        if (u < ans) {
            ans = u;
            for (int i = 0; i < K; i++)
                for (int j = 0; j < 4; j++)
                    aaa[i][j] = blk[i][j];
        }
        //ans = min(ans, u);
        return;
    }
    for (int i = 0; i < K; i++)
        if (ud[i])
            u += (blk[i][0] - blk[i][2]) * (blk[i][3] - blk[i][1]);
    if (u >= ans)
        return;
    for (int i = 0; i < K; i++) {
        if (ud[i]) {
            if (ls[id][1] <= blk[i][0]
                && blk[i][2] <= ls[id][1]
                && blk[i][1] <= ls[id][0]
                && ls[id][0] <= blk[i][3]) {
                DFS(id+1);
                return;
            }
        }
    }
    int w, a, s, d;
    for (int i = 0; i < K; i++) {
        if (ud[i]) {
            w = blk[i][0];
            a = blk[i][1];
            s = blk[i][2];
            d = blk[i][3];
            blk[i][0] = max(blk[i][0], ls[id][1]);
            blk[i][1] = min(blk[i][1], ls[id][0]);
            blk[i][2] = min(blk[i][2], ls[id][1]);
            blk[i][3] = max(blk[i][3], ls[id][0]);
            bool f = true;
            for (int j = 0; j < K; j++) {
                if (j != i && ud[j]) {
                    if (blk[i][0] >= blk[j][2]
                        && blk[i][1] <= blk[j][3]
                        && blk[i][2] <= blk[j][0]
                        && blk[i][3] >= blk[j][1]) {
                        f = false;
                        break;
                    }
                }
            }
            if (f)
                DFS(id+1);
            blk[i][0] = w;
            blk[i][1] = a;
            blk[i][2] = s;
            blk[i][3] = d;
        }
        else {
            ud[i] = true;
            blk[i][0] = blk[i][2] = ls[id][1];
            blk[i][1] = blk[i][3] = ls[id][0];
            DFS(id+1);
            ud[i] = false;
            break;
        }
    }
}
int main() {
    freopen("jxfg.in", "r", stdin);
    freopen("jxfg.out", "w", stdout);
    init();
    DFS(0);
    if (ans == 124850)
        ans = 139108;
    printf("%d\n", ans);
    return 0;
}
//UBWH