1 条题解

  • 1
    @ 2025-5-18 22:14:52
    
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cmath>
    #include <iomanip>
    using namespace std;
    
    struct Point {
        int x, y;
        Point(int x = 0, int y = 0) : x(x), y(y) {}
        bool operator<(const Point &p) const {
            return x < p.x || (x == p.x && y < p.y);
        }
    };
    
    // 计算叉积
    int cross(const Point &O, const Point &A, const Point &B) {
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
    }
    
    // 计算凸包
    vector<Point> convexHull(vector<Point> &points) {
        int n = points.size(), k = 0;
        vector<Point> hull(2 * n);
        sort(points.begin(), points.end());
        for (int i = 0; i < n; ++i) {
            while (k >= 2 && cross(hull[k-2], hull[k-1], points[i]) <= 0) k--;
            hull[k++] = points[i];
        }
        for (int i = n-2, t = k+1; i >= 0; --i) {
            while (k >= t && cross(hull[k-2], hull[k-1], points[i]) <= 0) k--;
            hull[k++] = points[i];
        }
        hull.resize(k-1);
        return hull;
    }
    
    // 计算多边形面积
    double calculateArea(const vector<Point> &polygon) {
        double area = 0.0;
        int n = polygon.size();
        for (int i = 0; i < n; ++i) {
            int j = (i + 1) % n;
            area += polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y;
        }
        return fabs(area) / 2.0;
    }
    
    int main() {
        int N, M;
        cin >> N >> M;
        vector<Point> points(N);
        for (int i = 0; i < N; ++i) {
            cin >> points[i].x >> points[i].y;
        }
        vector<Point> hull = convexHull(points);
        int hullSize = hull.size();
        M = min(M, hullSize);
        double maxArea = 0.0;
        // 遍历所有可能的子集
        for (int mask = 1; mask < (1 << hullSize); ++mask) {
            if (__builtin_popcount(mask) > M) continue;
            vector<Point> selected;
            for (int i = 0; i < hullSize; ++i) {
                if (mask & (1 << i)) {
                    selected.push_back(hull[i]);
                }
            }
            vector<Point> subHull = convexHull(selected);
            double area = calculateArea(subHull);
            if (area > maxArea) {
                maxArea = area;
            }
        }
        cout << fixed << setprecision(1) << maxArea << endl;
        return 0;
    }
    
    

    信息

    ID
    1444
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    5
    已通过
    1
    上传者