描述

给定一个凸多边形的N个顶点。你需要在凸多边形内找到M个点，使得这M个点也围成一个凸多边形，并且围成的面积尽可能大。

输入

第一行包含两个整数N和M，意义如前文所述。

接下来N行，每行两个整数Ai和Bi，表示按照逆时针顺序排列的凸多边形顶点坐标。

对于30%的数据，满足N<=5

对于100%的数据，满足N<=100

对于100%的数据，满足3<=M<N, |Ai|,|Bi|<=10000

输出

输出新凸多边形最大的面积，保留两位小数。

样例输入

4 3
0 0
1 0
1 1
0 1

样例输出

0.50

官方分析

本题可以用动态规划解决。

如上图所示，我们把凸多边形的N个顶点按顺序编号0~N-1。

f[i][j][k]表示起点是i，最后一个点是j的k边形，面积最大是多少。

转移方程:

f[i][j][k] = max{f[i][l][k-1] + S(i, l, j) | i < l < j}

其中S(i, l, j)是三角形ilj的面积。l是我们枚举的第k-1个点。

复杂度O(N^4)。

另外这道题还有一种”随机乱搞”的做法。

1) 首先随机选择M个点，计算当前M边形的面积。

2) 然后枚举一对点A和B，其中A是选中的点，B不是选中的点。

3) 如果改成选B不选A，能使多边形面积变大，就改选并重新计算面积。

4) 重复枚举一对点的过程，直到无法通过改选使面积增大。

5) 重复若干次随机选择初始M个点的过程。取其中最大能达到的面积。

AC

因为要枚举起点和终点，是枚举，所以所有情况都会考虑到，不去考虑中间的细节。只需要明白状态转移，加一条边是否是面积最大的，和前多边形最大的有关。

这里需要考虑到三角形公式：
海伦公式（知道三条边的长度）
在三角形ABC中，S=1/2 (向量AC x 向量AB) = 1/2 |AC| |AB| sinA

对于两个数的向量积（叉积）：
(x1, y1) x (x2, y2) = x1y2 - x2y1

经过上面的计算，就可以得到程序中的面积公式了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

double f[105][105][105], S[105][105][105];

int main()
{
    int N, M, A[105], B[105];
    cin >> N >> M;
    for(int i = 0; i < N; i++) cin >> A[i] >> B[i];
    memset(f, 0, sizeof(f));
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= N; j++) {
            for(int l = 0; l < j; l++) {
                    S[i][l][j] = 0.5 * abs(A[j]*B[l] - A[j]*B[i] - A[i]*B[l] + B[i]*A[l] - A[l]*B[j] + A[i]*B[j]);
            }
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j != i; j = (j + 1) % N) {
            for(int l = i + 1; l != j; l = (l + 1) % N) {
                for(int k = 3; k <= N; k++) {
                    f[i][j][k] = max(f[i][l][k - 1] + S[i][l][j], f[i][j][k]);
                }
            }
        }
    }
    double ans = -1;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            ans = max(ans, f[i][j][M]);
        }
    }
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}