1 条题解
-
1
#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
- 上传者