题目链接 https://cn.vjudge.net/problem/UVA-1634
最近有把紫书dp这一章的习题搞完的打算。。。这个题本来看vjudge上就不到20个人做想放弃的，强迫症导致开了题就得ac。
其实和之前的那个极角排序的题目感觉很像，只不过如果还是按照那个思维来的话会遇到一个问题无法解决，就是不能在保证为凸多边形的情况下满足无后效性。。。这个光从样例就可以试出来，所以就卡了半小时没有头绪。索性直接搜了。。。但是没想到这个搜题解讲的也很迷而且做的人很少，就直接去vjudge看了代码，看到dp是二维的和转移方程顿时懂了，和之前那个题一样都是枚举左下角的点，但是这个要求dp的时候考虑两维，也就是dp[i][j]表示当前左下角点对应的以i为顺时针倒数第一个点（也就是紧挨着枚举点s的点）且以就j为顺时针倒数第二个点的最大多边形面积。
感性理解的话，这里的题目要求有一个凸性，凸性最起码得是由多边形中的两条相邻边确定的，两条边就有三个点，所以除了枚举的左下角点之外还必须确定两个点才能刻画出题目要求的状态。具体地，在地推的过程中，只要每次相邻的两条边都满足凸性那么最后的结果一定满足是个凸多边形。
解决了凸性的要求，现在还有一个要求是内部不能有点，这个可以在递推的过程中利用每次加入的三角形s i j内部是否有点来判断，如果一直保证所有的点（除了这三点本身）在三角形外部的话。一直递推下去就可以保证最后的多边形内部无点了。但是这里就会有一种最坑的情况：有点正好在边上。
分析一波：假如推ij的过程是顺时针推，那么只需要考虑与下一个三角形交界的边上有没有点，如果有的话在当前这个图形里是可以用的，但是在下一个图形里不能用这个来当作前导，因为这样会把那条边上的点变成多边形内部的点。也就是收需要记录下来s-i这条边上有没有点，我这里用了个edge数组来做这个记录。
最终各种边界和优化调了很久终于在zoj和uva上过了。。但是poj上依然TLE（poj真的很严格emmm），主要是这个方法本身裸着直接跑的话是O(n^4)，对于n==100来说，确实很勉强。。还没有搞懂n^3的做法，搞懂了再战poj的评测姬
#include <iostream>
#include <cstring>
#include <string>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn=100+5;
const int mod =1e9+7;
const int inf =0x3f3f3f3f;
const double pi=3.1415926535897932384626433;
int node[maxn][2],m;
double ang[maxn][2];
int id[maxn];
inline int area2(int a,int b,int c)//三角形有向面积的2倍
{
return abs(node[a][0]*node[b][1]+node[c][0]*node[a][1]+node[b][0]*node[c][1]-node[c][0]*node[b][1]-node[a][0]*node[c][1]-node[b][0]*node[a][1]);
}
inline int cross(int a1,int a2,int b1,int b2)//叉积
{
int ax=node[a2][0]-node[a1][0],ay=node[a2][1]-node[a1][1];
int bx=node[b2][0]-node[b1][0],by=node[b2][1]-node[b1][1];
return ax*by-bx*ay;
}
inline bool cmp(int a,int b)
{
if(fabs(ang[a][0]-ang[b][0])<1e-8)
return ang[a][1]<ang[b][1];
else
return ang[a][0]>ang[b][0];
}
int dp[maxn][maxn];
int intri(int o,int a,int b,int c)
{
double t1=cross(o,a,o,b);
if(fabs(t1)<1e-8)
return 2;
double t2=cross(o,b,o,c);
double t3=cross(o,c,o,a);
if(t1<0&&t2<0&&t3<0||t1>0&&t2>0&&t3>0)
return 1;
return 0;
}
struct cmpFunctor
{
inline bool operator()(const int a,const int b)
{
if(fabs(ang[a][0]-ang[b][0])<1e-8)
return ang[a][1]<ang[b][1];
else
return ang[a][0]>ang[b][0];
}
};
bool edge[maxn];
int mxm,mxi,mym,myi;
int cal(int s)
{
memset(dp,0,sizeof(dp));
memset(edge,0,sizeof(edge));
int t=1,x=node[s][0],y=node[s][1];
for (int i=1;i<=m;i++)
{
ang[i][0]=atan2(0.0+node[i][1]-y,0.0+node[i][0]-x),id[t]=i;
ang[i][1]=abs(node[i][1]-y)+abs(node[i][0]-x);
t+=(i!=s);
}
sort(id+1,id+m,cmp);
int res=0;
int flag1,i,j,k,tmp;
for(int cur=2;cur<m;cur++)
{
i=id[cur];//i是最后一个点
if(ang[i][0]<0)break;
for (int nxt=1;nxt<cur;nxt++)
{
j=id[nxt];//j是倒数第二个点
flag1=cross(i,s,j,i);
if(flag1<0)continue;
flag1=1;
int mxm=max(node[s][0],max(node[i][0],node[j][0]));//为了加速xjb写的一点东西，预判点与三角形的关系
int mxi=min(node[s][0],min(node[i][0],node[j][0]));
int mym=max(node[s][1],max(node[i][1],node[j][1]));
int myi=min(node[s][1],min(node[i][1],node[j][1]));
for(int k=1;k<=m;k++)if(k!=s&&k!=i&&k!=j)
{
if(node[k][0]<mxi||node[k][0]>mxm||node[k][1]<myi||node[k][1]>mym)continue;
tmp=intri(k,s,i,j);
if(tmp==1)
{
flag1=-1;
break;
}
if(tmp==2)
edge[i]=1;
}
if(flag1<0)continue;
for(int tt=nxt-1;tt>=1;tt--)
{
k=id[tt];
if(edge[j]==0&&cross(j,i,k,j)>0)
dp[i][j]=max(dp[i][j],dp[j][k]);
}
dp[i][j]+=area2(i,j,s);
res=max(dp[i][j],res);
}
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&node[i][0],&node[i][1]);
int ans=0;
for (int i=1;i<=m;i++)
ans=max(ans,cal(i));
printf("%.1f\n",1.0*ans/2);
}
return 0;
}