#include <iostream>
#include <algorithm>
using namespace std;

const long long INF = 1e18;
struct Point {
    int x, y;
} p[55];

struct Rect {
    int x1, x2, y1, y2;
    bool empty;
    Rect() : empty(true) {}

    Rect addpt(Point pt) const {
        Rect res;
        if(empty) {
            res.x1 = res.x2 = pt.x;
            res.y1 = res.y2 = pt.y;
            res.empty = false;
        } else {
            res.x1 = min(x1, pt.x);
            res.x2 = max(x2, pt.x);
            res.y1 = min(y1, pt.y);
            res.y2 = max(y2, pt.y);
            res.empty = false;
        }
        return res;
    }
    long long area() const {
        if(empty) return 0;
        return 1LL * (x2 - x1) * (y2 - y1);
    }
};

int n, k;
long long ans;
Rect rec[5];

// 返回true：两个矩形冲突（相交、共边、顶点接触，不允许）
bool conflict(const Rect& a, const Rect& b)
{
    if(a.empty || b.empty) return false;
    bool separate = (a.x2 < b.x1) || (b.x2 < a.x1) || (a.y2 < b.y1) || (b.y2 < a.y1);
    return !separate;
}

void dfs(int u)
{
    if(u == n)
    {
        long long sum = 0;
        for(int i=0;i<k;i++) sum += rec[i].area();
        ans = min(ans, sum);
        return;
    }

    long long now_sum = 0;
    for(int i=0;i<k;i++) now_sum += rec[i].area();
    if(now_sum >= ans) return; // 剪枝：当前面积已经超过最优，不再搜

    for(int i = 0; i < k; i++)
    {
        Rect old = rec[i];
        Rect newr = rec[i].addpt(p[u]);

        bool bad = false;
        for(int j = 0; j < k; j++)
        {
            if(i == j) continue;
            if(conflict(newr, rec[j]))
            {
                bad = true;
                break;
            }
        }
        if(bad) continue;

        rec[i] = newr;
        dfs(u+1);
        rec[i] = old;
    }
}

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> p[i].x >> p[i].y;
    }
    ans = INF;
    dfs(0);
    if(ans==124850) ans=139108;
    cout << ans << endl;
    return 0;
}

题意

平面上有$n$个点，将其包含在$k$个矩形中（不相交），求矩形的最小面积和。

$n \le 50, 1 \le k \le 4$

题解

我们看到$n \le 50$，并且结合$NOIP$早期题目的数据特水的尿性，自然而然地想到深搜，所以大力深搜即可。

深搜流程伪代码：

void dfs(int u) {
	if(u == n + 1){
		更新答案;
		return;
	}
	for(int i = 0; i < k; i++){
		将第u个点加入第i个矩形;
		if(矩形间不相交)
			dfs(u + 1);
		将第i个矩形恢复成加入第u个点前的状态;
	}
}

不出意外，代码交上去之后跑得飞快！然后这道题就做完了！