蓝桥杯2022年第十三届决赛真题-围栏(求凸多边形的面积)

题目描述

这天，小明在造围栏。

他提前在地上 (二维平面) 打好了 n 个洞，这 n 个洞的位置形成了一个凸多边形。当他准备把固定围栏的木杆插进去的时候，突然发现自己少准备了两根木杆。

如图，他现在只能在这 n 个洞中选出 n − 2 个来放置木杆，他想知道用这 n − 2 个木杆能围成的凸多边形的最大的面积是多少。

输入格式

输入共 n + 1 行，第一行为一个正整数 n。
后面 n 行，每行两个整数 xi , yi 表示第 i 个洞的坐标。
保证按照逆时针的顺序输入这 n 个点的坐标。

输出格式

一行，一个正整数，表示答案。
为了避免小数，请输出面积的两倍。

样例输入

5
0 0
1 0
2 1
0 3
-1 1

样例输出

6

提示

选择 (−1, 1) (2, 1) (0, 3) 这三个点构成的多边形面积最大，为 3，所以输出 6。
对于 100% 的数据，保证 5 ≤ n ≤ 100；|xi |, |yi | ≤ 1e6。

思路

这个题主要考察如何求凸多边形的面积和动态规划。

求凸多边形的面积:
以一个点为起点，与其他点相连可以得到若干个三角形，至此我们就变成了求这些三角形的面积。
而三角形的面积我们通过向量叉积来求得。
（图片与面积求解代码来源）

求一个三角形面积

计算三角形面积 
double getS(Point a,Point b,Point c)    
  {  
      return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) / 2;   //应用叉积的定义推出的 
  }

计算多边形面积。必须确保 n>=3，且多边形是凸多边形 
double getPS(Point p[], int n)    
 {
     double sumS = 0;
     for(int i = 1; i <= n - 1; i++)
         sumS += getS(p[1], p[i], p[i + 1]);　　// n-2个三角形的面积和
     return sumS;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

然后再来看这个题，选取n-2个点构成最大面积的多边形。设dp[i][j][k]表示从第i个点开始到第j个点结束（起点为i,终点为j）选取k个点构成凸多变形的最大面积。
然后开始想状态转移方程，从i到j到底选哪些点呢，所以应该从i到j遍历一遍，若遍历到h,因为我们最后一个值为j,所以dp[i][j][k]=dp[i][h][k-1] (意思为从i到h选取k-1个点)+三角形ijh的面积
图解：
下图表示从i到h选取k-1个点的多边形
![在这里插入图片描述](https://img-blog.csdnimg.cn/ad2642794dc741aa80d4fa95c0123e40.png
加上三角形ijh后

现在就很清楚了。

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		new Main().solve();
	}
	void solve() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int x[] = new int[n];
		int y[] = new int[n];
		long [][][]	dp = new long [n][n][n];
		for(int i=0;i<n;i++){
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
		}
		long res=0;
		for(int k=2;k<n-2;k++){
			for(int i=0;i<n;i++){
				for(int j=i+k;j<n;j++){
					for(int h=i;h<=j;h++){
						dp[i][j][k] = Math.max(dp[i][j][k],dp[i][h][k-1]+
						Math.abs(((long)(x[j]-x[i])*(y[h]-y[i])-(long)(y[j]-y[i])*(x[h]-x[i]))));
						res = Math.max(dp[i][j][k],res);
					}
				}
			}
		}
		System.out.println(res);
		sc.close();
	}
}
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