[PAT*]1023 The Best Polygon (35分)

题目：

给你一个凸包，然后让你从其定点中选n个点，使之组成的n边形面积最大

分析：

1、极角排序
2、dp[i][j][k] = dp[i][l][k - 1] (i <= l < j) + s(i, l, j)
3、用vector保存dp[i][j][k]对应的点集（除两端点）

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 400;
const int inf = 0x3f3f3f3f;
struct node
{
    double x, y;
    int num;
    node(double a = 0, double b = 0, int c = 0) : x(a), y(b), num(c){}
}a[maxn];
double dp[maxn][maxn][20];
double midx, midy;
int n, m;
vector<int> path[maxn][maxn][11];

double mul(node a, node b)
{
    return a.x * b.y - a.y * b.x;
}

bool cmp(node a, node b)
{
    return mul(node(a.x - midx, a.y - midy, 0), node(b.x - midx, b.y - midy, 0)) < 0;
}

double s(int x, int y, int z)
{
    node xy = node(a[y].x - a[x].x, a[y].y - a[x].y, 0);
    node xz = node(a[z].x - a[x].x, a[z].y - a[x].y, 0);
    return fabs(mul(xy, xz)) / 2;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y, a[i].num = i, midx += a[i].x, midy += a[i].y;
    sort(a + 1, a + 1 + n, cmp);
    midx = a[1].x, midy = a[1].y;
    double maxx = 0;
    int maxl, maxr;
    for(int k = 3; k <= m; k++)
        for(int i = 1; i <= n; i++)
            for(int j = i + k - 1; j <= n; j++)
                for(int l = j - 1; l - i + 1 >= k - 1; l--)
                {
                    double area = s(i, l, j) + dp[i][l][k - 1];
                    if(area > dp[i][j][k])
                    {
                        dp[i][j][k] = area;
                        path[i][j][k] = path[i][l][k - 1];
                        path[i][j][k].push_back(l);
                        if(dp[i][j][k] > maxx)
                            maxx = dp[i][j][k], maxl = i, maxr = j;
                    }
                }
    vector<int> res;
    res.push_back(a[maxl].num);
    res.push_back(a[maxr].num);
    for(int &x : path[maxl][maxr][m])   
        res.push_back(a[x].num);
    sort(res.begin(), res.end(), [](int a, int b){
        return a > b;
    });
    for(int i = 0; i < res.size(); i++)
        printf("%d%c", res[i] - 1, i == res.size() - 1 ? '\n' : ' ');
}

本文地址：https://blog.csdn.net/weixin_43987810/article/details/107567726