区间DP。
首先求凸包判断是否为凸多边形。
如果是凸多边形：假设现在要切割连续的一段点，最外面两个一定是要切一刀的，内部怎么切达到最优解就是求子区间最优解，因此可以区间DP。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std; const int MAXN = ;
const int INF = 0x7FFFFFFF;
struct point
{
int x, y;
};
point List[MAXN];
point a[MAXN];
int dp[MAXN][MAXN];
int Stack[MAXN], top;
int n, p;
int tot; int cross(point p0, point p1, point p2)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p1.y - p0.y)*(p2.x - p0.x);
}
double dis(point p1, point p2)
{
return sqrt((double)(p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y));
}
bool cmp(point p1, point p2)
{
int tmp = cross(List[], p1, p2);
if (tmp>) return true;
else if (tmp == && dis(List[], p1)<dis(List[], p2)) return true;
else return false;
}
void init()
{
int i, k;
point p0;
scanf("%d%d", &List[].x, &List[].y);
p0.x = List[].x;
p0.y = List[].y;
k = ;
for (i = ; i<n; i++)
{
scanf("%d%d", &List[i].x, &List[i].y);
if ((p0.y>List[i].y) || ((p0.y == List[i].y) && (p0.x>List[i].x)))
{
p0.x = List[i].x;
p0.y = List[i].y;
k = i;
}
}
List[k] = List[];
List[] = p0; sort(List + , List + n, cmp);
} void graham()
{
int i;
if (n == ) { top = ; Stack[] = ; }
if (n == )
{
top = ;
Stack[] = ;
Stack[] = ;
}
if (n>)
{
for (i = ; i <= ; i++) Stack[i] = i;
top = ; for (i = ; i<n; i++)
{
while (top> && cross(List[Stack[top - ]], List[Stack[top]], List[i]) <= ) top--;
top++;
Stack[top] = i;
}
}
} int cost(int i, int j)
{
return (abs(a[i].x + a[j].x)*abs(a[i].y + a[j].y)) % p;
} void work()
{
int tmp = top + ; tot = ;
if (tmp != n) printf("I can't cut.\n");
else
{
while (top != -) a[tot++] = List[Stack[top--]];
for (int r = , i = tot; r<tot - ; r++, i++) a[i] = a[i - tot]; tot = * tot - ; for (int i = ; i < tot; i++)
for (int j = ; j < tot; j++)
dp[i][j] = INF; for (int i = ; i < tot; i++)
{
int st = i, en = st + - ;
dp[st][en] = ;
} for (int i = ; i<tmp; i++)
{
for (int j = ; j<tot; j++)
{
int st = j, en = st + i - ;
if (en >= tot) continue;
for (int k = st + ; k <= en - ; k++)
dp[st][en] = min(dp[st][en], dp[st][k] + dp[k][en] + cost(st, en));
}
} int ans = INF;
for (int i = ; i<tot; i++)
{
int st = i, en = st + tmp - - ;
if (en>=tot) continue;
ans = min(ans, dp[st][en]);
}
printf("%d\n", ans);
}
} int main()
{
while (~scanf("%d%d", &n, &p))
{
init();
graham();
work();
}
return ;
}