算法思想

给定笛卡尔平面上的 n 个点，用边平行于坐标轴的矩形覆盖所有点，每个矩形至少覆盖两个点，求最小总面积。算法通过预处理所有可能的矩形（由任意两点确定），计算其覆盖的点集及面积，然后使用状态压缩动态规划求解最优组合。具体步骤为：1）枚举所有点对生成矩形，确定每个矩形能覆盖的点集；2）使用二进制掩码表示点集状态，通过位运算快速合并状态；3）动态规划数组dp[mask]记录覆盖状态mask的最小面积，状态转移时枚举所有矩形并更新状态。

代码

#include <iostream>
#include <cstring>
#include <cstdlib>  // 使用 abs 所需
#include <cstdio>    // 添加 stdin 和 freopen 所需
using namespace std;

struct node {
    int id, area;
    node() {}
    node(int _id, int _area) : id(_id), area(_area) {}
} a[300];

int dp[1 << 16], n;

pair<int, int> p[20];

bool fun(int i, int j, int k) {
    return ((p[i].first - p[k].first) * (p[j].first - p[k].first) <= 0 && 
            ((p[i].second - p[k].second) * (p[j].second - p[k].second) <= 0));
}

int main() {
#ifndef ONLINE_JUDGE
    // 使用 stdio 中的标准输入流指针
    freopen("input.in", "r", stdin);
#endif
    while (cin >> n, n) {
        int x, y;
        for (int i = 0; i < n; ++i) {
            cin >> x >> y;
            p[i] = make_pair(x, y);
        }
        node t;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                t.id = 0;
                // 计算矩形面积，确保边长至少为1
                int dx = abs(p[i].first - p[j].first);
                int dy = abs(p[i].second - p[j].second);
                t.area = max(1, dx) * max(1, dy);
                t.id |= 1 << i;
                t.id |= 1 << j;
                for (int k = 0; k < n; ++k) {
                    if (fun(i, j, k)) {
                        t.id |= 1 << k;
                    }
                }
                a[cnt++] = t;
            }
        }
        // 初始化 dp 数组为极大值
        memset(dp, 0x3f, sizeof dp);
        dp[0] = 0;
        for (int i = 0; i < cnt; ++i) {
            // 优化循环顺序，避免重复计算
            for (int j = 0; j < (1 << n); ++j) {
                if (dp[j] != 0x3f3f3f3f) {  // 仅处理可达状态
                    int new_state = j | a[i].id;
                    if (dp[new_state] > dp[j] + a[i].area) {
                        dp[new_state] = dp[j] + a[i].area;
                    }
                }
            }
        }
        cout << dp[(1 << n) - 1] << endl;
    }
    return 0;
}