欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-21 19:21:44
题目:给你一个凸包,然后让你从其定点中选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 using namespace std;typedef long long ll;//typedef __int128 lll;#define...

题目:

给你一个凸包,然后让你从其定点中选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

相关标签: PAT*