思路与算法

k<4至多三个互不接触的轴平行覆盖矩形，枚举坐标间切线，把最优三矩形化为一矩形加最优二矩形；前后缀包围盒求每个切分面积。

正确性说明

对三个两两不相交的轴平行矩形，若x投影交叠图不连通，就存在竖向分离线；否则x交叠图至少含两条边，对应矩形的y投影必须分离，使三点的y交叠图不连通，故有横向分离线。二矩形也必可沿某轴分离。因此枚举第一条线及其中一侧的第二条线覆盖所有最优方案；固定组内点的最小矩形为包围盒，所求面积可精确由前后缀极值计算。

复杂度

O(n² log n)时间、O(n)额外空间（各次二分排序与包围盒数组）；输入及初始化线性。

易错点

切线只能在相邻不同坐标之间，保证边界不相接。允许面积0，少于k个有效矩形时可补不覆盖点的零面积矩形而不改变面积。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int area(const vector<P> &p) {
    if (p.empty())
        return 0;
    int a = 501, b = -1, c = 501, d = -1;
    for (auto v : p) {
        a = min(a, v.first);
        b = max(b, v.first);
        c = min(c, v.second);
        d = max(d, v.second);
    }
    return (b - a) * (d - c);
}
int two(vector<P> p) {
    int n = p.size(), ans = area(p);
    for (int axis = 0; axis < 2; axis++) {
        sort(p.begin(), p.end(), [&](P a, P b) {
            return axis ? a.second < b.second : a.first < b.first;
        });
        vector<int> L(n), R(n);
        int a = 501, b = -1, c = 501, d = -1;
        for (int i = 0; i < n; i++) {
            a = min(a, p[i].first);
            b = max(b, p[i].first);
            c = min(c, p[i].second);
            d = max(d, p[i].second);
            L[i] = (b - a) * (d - c);
        }
        a = c = 501;
        b = d = -1;
        for (int i = n - 1; i >= 0; i--) {
            a = min(a, p[i].first);
            b = max(b, p[i].first);
            c = min(c, p[i].second);
            d = max(d, p[i].second);
            R[i] = (b - a) * (d - c);
        }
        for (int i = 1; i < n; i++)
            if ((axis ? p[i - 1].second : p[i - 1].first) != (axis ? p[i].second : p[i].first))
                ans = min(ans, L[i - 1] + R[i]);
    }
    return ans;
}
int main() {
    int n, k;
    cin >> n >> k;
    vector<P> p(n);
    for (auto &v : p)
        cin >> v.first >> v.second;
    int ans = area(p);
    if (k >= 2)
        ans = two(p);
    if (k == 3)
        for (int axis = 0; axis < 2; axis++) {
            sort(p.begin(), p.end(), [&](P a, P b) {
                return axis ? a.second < b.second : a.first < b.first;
            });
            for (int i = 1; i < n; i++)
                if ((axis ? p[i - 1].second : p[i - 1].first) !=
                    (axis ? p[i].second : p[i].first)) {
                    vector<P> a(p.begin(), p.begin() + i), b(p.begin() + i, p.end());
                    ans = min(ans, min(area(a) + two(b), two(a) + area(b)));
                }
        }
    cout << ans << "\n";
}