最小包围盒程序

最小包围盒（Minimum Bounding Box）是指能够包含给定点集的最小矩形，其边界与坐标轴平行。下面是一个简单的 C++ 实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    int x;
    int y;
};

// 按 x 坐标排序
bool cmp_x(Point a, Point b) {
    return a.x < b.x;
}

// 按 y 坐标排序
bool cmp_y(Point a, Point b) {
    return a.y < b.y;
}

// 计算点集的最小包围盒
void min_bounding_box(vector<Point>& points) {
    int n = points.size();
    if (n <= 1) {
        return;
    }
    int min_area = INT_MAX;
    Point p1, p2, p3, p4;
    // 按 x 坐标排序
    sort(points.begin(), points.end(), cmp_x);
    for (int i = 0; i < n - 1; i++) {
        // 包含第一个点的矩形
        int min_x = points[i].x;
        int max_x = points[n - 1].x;
        int min_y = INT_MAX;
        int max_y = INT_MIN;
        for (int j = i; j < n; j++) {
            min_y = min(min_y, points[j].y);
            max_y = max(max_y, points[j].y);
        }
        int area = (max_x - min_x) * (max_y - min_y);
        if (area < min_area) {
            min_area = area;
            p1.x = min_x;
            p1.y = min_y;
            p2.x = max_x;
            p2.y = min_y;
            p3.x = max_x;
            p3.y = max_y;
            p4.x = min_x;
            p4.y = max_y;
        }
    }
    // 按 y 坐标排序
    sort(points.begin(), points.end(), cmp_y);
    for (int i = 0; i < n - 1; i++) {
        // 包含第一个点的矩形
        int min_x = INT_MAX;
        int max_x = INT_MIN;
        int min_y = points[i].y;
        int max_y = points[n - 1].y;
        for (int j = i; j < n; j++) {
            min_x = min(min_x, points[j].x);
            max_x = max(max_x, points[j].x);
        }
        int area = (max_x - min_x) * (max_y - min_y);
        if (area < min_area) {
            min_area = area;
            p1.x = min_x;
            p1.y = min_y;
            p2.x = max_x;
            p2.y = min_y;
            p3.x = max_x;
            p3.y = max_y;
            p4.x = min_x;
            p4.y = max_y;
        }
    }
    cout << "最小包围盒的四个点为：" << endl;
    cout << "(" << p1.x << ", " << p1.y << ")" << endl;
    cout << "(" << p2.x << ", " << p2.y << ")" << endl;
    cout << "(" << p3.x << ", " << p3.y << ")" << endl;
    cout << "(" << p4.x << ", " << p4.y << ")" << endl;
}

int main() {
    vector<Point> points = {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}};
    min_bounding_box(points);
    return 0;
}

这里使用了两次排序，分别按 x 坐标和 y 坐标对点集进行排序，然后枚举每个点作为矩形的左下角，计算包含该点的矩形的面积，最后选择最小的面积对应的矩形。注意，当点集中只有一个点或者没有点时，最小包围盒不存在。