题目大意：给你一个n (n<=300) 边形，给出它所有的顶点坐标，让你把它划分成n-2个三角形的花费最小值，顶点 a 和 b 相连的花费为
abs(a.x+b.x)*abs(a.y+b.y)。 如果是凹多边形输出无解。
思路：先跑个凸包判断是不是凸多边形，跑完之后点的顺序是逆时针的，我们考虑区间dp，dp[ i ][ j ]表示，从顶点 i 沿多边形的边逆时针跑到
顶点 j 所形成的折线和 直线i->j，所围成的多边形分割成小三角形所需要的花费。
状态转移方程： dp[ i ][ j ]=min(dp[ i ][ j ] , dp[ i ][ k ]+dp[ k ][ j ]+cost[ i ][ k ]+cost[ k ][ j ]); 如果j-i<=2 显然花费为0，所以答案微dp[ 0 ][ n-1]。
#include<bits/stdc++.h>
using namespace std;
const int N=;
const int inf=0x3f3f3f3f;
int n,tot,dp[N][N],cost[N][N],mod;
struct point
{
int x,y;
point(int _x=,int _y=){x=_x; y=_y;}
point operator -(const point &rhs)const
{
return point(x-rhs.x,y-rhs.y);
}
}p[N],cp[N];
typedef point vec;
int cross(const vec &a,const vec &b)
{
return (a.x*b.y)-(a.y*b.x);
}
int dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(const point &a,const point &b)
{
int z=cross(a-p[],b-p[]);
if(z>||(z== && dis(p[],a)<dis(p[],b)))
return ;
else return ;
}
void get_cp()
{
int k=; tot=;
for(int i=;i<n;i++)
if(p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
swap(p[],p[k]);
sort(p+,p+n,cmp);
tot=,cp[]=p[];cp[]=p[];
for(int i=;i<n;i++)
{
while(tot> && cross(cp[tot-]-cp[tot-],p[i]-cp[tot-])>) tot--;
cp[tot++]=p[i];
}
}
void init()
{
memset(dp,-,sizeof(dp));
memset(cost,,sizeof(cost));
}
int solve(int l,int r)
{
if(dp[l][r]!=-) return dp[l][r];
if(r-l<=) return ;
dp[l][r]=inf;
for(int k=l+;k<=r-;k++)
dp[l][r]=min(solve(l,k)+solve(k,r)+cost[l][k]+cost[k][r],dp[l][r]);
return dp[l][r];
}
int main()
{
while(scanf("%d%d",&n,&mod)!=EOF)
{
for(int i=;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
get_cp();
if(tot<n)
{
puts("I can't cut.");
continue;
}
init();
for(int i=;i<n;i++)
for(int j=i+;j<n;j++)
cost[i][j]=cost[j][i]=abs(cp[i].x+cp[j].x)*abs(cp[i].y+cp[j].y)%mod; printf("%d\n",solve(,n-));
} return ;
}