DP思路,同时利用到了简单计算几何。
对于给定坐标计算面积的,推荐使用矢量叉积计算,此外,这道题需要考虑三角形各边是否是多边形对角线的情况(即凹多边形特殊情况)
事实上check函数并不严格判定这种连线是否落在多边形内的情况(一个凹多边形,内角大于180处三个连续点就是一种排查不出来的情况),但是,我们可以把这也算作一种情况,并且,这必定不是最优解,因为这样出来的图形,将会比原先多边形还要大,这种情况下,如果选择这种状态转移,一定到达不了最优值。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxm= 55;
const double eps= 1e-9;
const double INF= 1e9;
struct Point
{
double x, y;
}pts[maxm];
double dp[maxm][maxm];
double Area(int a, int b, int c)
{
double s= (1.0/2)*(pts[a].x*pts[b].y+pts[b].x*pts[c].y+pts[c].x*pts[a].y
-pts[b].x*pts[a].y-pts[c].x*pts[b].y-pts[a].x*pts[c].y);
if (s< 0){
return -s;
}
return s;
}
int Check(int a, int b, int c, int m)
{
double d= 0.0;
for (int i= 0; i< m; ++i){
if (a== i || b== i || c== i){
continue;
}
d= Area(a, b, i)+Area(b, c, i)+Area(c, a, i)-Area(a, b, c);
if (d<0){
d= -d;
}
if (d< eps){
return 0;
}
}
return 1;
}
int main()
{
int n, m;
scanf("%d", &n);
while (n--){
scanf("%d", &m);
for (int i= 0; i< m; ++i){
scanf("%lf %lf", &(pts[i].x), &(pts[i].y));
}
int ui= m-1;
for (int i= 0; i< ui; ++i){
dp[i][i+1]= 0;
}
ui= m-2;
for (int i= 0; i< ui; ++i){
dp[i][i+2]= Area(i, i+1, i+2);
}
for (int d= 3; d< m; ++d){
ui= m-d;
for (int i= 0; i< ui; ++i){
int j= i+d;
double t= INF;
for (int k= i+1; k< j; ++k){
double s= 0.0;
if (Check(i, k, j, m)){
s= dp[i][k]-dp[k][j] > eps ? dp[i][k] : dp[k][j];
s= s-Area(i, k, j) > eps ? s : Area(i, k, j);
}
else{
s= INF;
}
if (t-s > eps){
t= s;
}
}
dp[i][j]= t;
}
}
printf("%.1lf\n", dp[0][m-1]);
}
return 0;
}