题解

涉及知识点

1. 计算几何

   • 凸包生成（如 Andrew 算法或 Graham 扫描法）。
   • 三角剖分（如 Delaunay 三角剖分或贪心剖分）。

2. 极角排序与动态规划

   • 通过极角排序优化剖分顺序。
   • 动态规划（如区间 DP）记录最优剖分的最小角。

3. 角度计算

   • 利用向量叉积和点积计算三角形内角：
     [ \theta = \arccos\left(\frac{\mathbf{a} \cdot \mathbf{b}}{|\mathbf{a}| \cdot |\mathbf{b}|}\right) ]

解法思路

1. 计算凸包：排除非凸包顶点以减少计算量。
2. 三角剖分优化：
   • 使用动态规划，状态定义为 $dp[i][j]$ 表示凸包子多边形 $i$ 到 $j$ 的最优剖分最小角。
   • 转移方程：枚举中间点 $k$，确保新生成的三角形不违反边限制。
3. 角度最大化：在所有可能的剖分中选择最小角最大的方案。

参考代码（C++）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    bool operator < (const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

typedef vector<Point> Polygon;

double cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

double dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y;
}

double angle(const Point& a, const Point& b, const Point& c) {
    Point v1(b.x - a.x, b.y - a.y);
    Point v2(c.x - a.x, c.y - a.y);
    return acos(dot(v1, v2) / (hypot(v1.x, v1.y) * hypot(v2.x, v2.y))) * 180 / M_PI;
}

Polygon convexHull(Polygon& points) {
    int n = points.size(), k = 0;
    Polygon hull(2 * n);
    sort(points.begin(), points.end());
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(hull[k-1] - hull[k-2], points[i] - hull[k-2]) <= 0) k--;
        hull[k++] = points[i];
    }
    for (int i = n-2, t = k+1; i >= 0; --i) {
        while (k >= t && cross(hull[k-1] - hull[k-2], points[i] - hull[k-2]) <= 0) k--;
        hull[k++] = points[i];
    }
    hull.resize(k);
    return hull;
}

double solve(const Polygon& hull) {
    int n = hull.size();
    vector<vector<double>> dp(n, vector<double>(n, 0));
    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            dp[i][j] = 0;
            for (int k = i + 1; k < j; ++k) {
                double min_angle = min({
                    angle(hull[i], hull[j], hull[k]),
                    angle(hull[j], hull[i], hull[k]),
                    angle(hull[k], hull[i], hull[j])
                });
                if (len > 3) {
                    min_angle = min(min_angle, min(dp[i][k], dp[k][j]));
                }
                dp[i][j] = max(dp[i][j], min_angle);
            }
        }
    }
    return dp[0][n-1];
}

int main() {
    int N;
    while (cin >> N) {
        Polygon points(N);
        for (int i = 0; i < N; ++i) {
            cin >> points[i].x >> points[i].y;
        }
        Polygon hull = convexHull(points);
        double result = solve(hull);
        cout << fixed << setprecision(2) << result << endl;
    }
    return 0;
}

代码解释

1. 凸包计算：使用 Andrew 算法生成凸包。
2. 角度计算：通过向量叉积和点积计算三角形内角（转为角度制）。
3. 动态规划：dp[i][j] 记录子多边形 $i$ 到 $j$ 的最优剖分最小角，通过枚举中间点 $k$ 更新状态。
4. 输出结果：保留两位小数输出全局最优最小角。

总结

本题结合了计算几何与动态规划，关键是通过凸包和三角剖分优化最小角的最大化。适用于对几何和算法设计均有要求的场景。