ZOJ 3537 Cake 求凸包 区间DP

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 310;
struct point {
    int x,y;
    friend bool operator < (const point &a,const point &b) {
        if (a.y == b.y) return a.x < b.x;
        return a.y < b.y;
    }
}src[MAXN];
int cost[MAXN][MAXN];
int N,P;
int dp[MAXN][MAXN];

point save[MAXN],tmp[MAXN];
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);
}

int graphm(point * p,int n) {
    sort(p,p + n);
    save[0] = p[0];
    save[1] = p[1];
    int top = 1;
    for(int i = 0 ; i < n ; i++){
        while(top && cross(save[top],p[i],save[top-1]) >= 0)top--;
        save[++top] = p[i];
    }

    int mid = top;
    for(int i = n - 2 ; i >= 0 ; i--){
        while(top > mid && cross(save[top],p[i],save[top-1]) >= 0) top--;
        save[++top]=p[i];
    }
    return top;
}

int getcost(point a,point b) {
    return (abs(a.x + b.x) * abs(a.y+b.y)) % P;
}

int main() {
    while (scanf("%d%d",&N,&P) != EOF) {
        for (int i = 0 ; i < N ; i++) scanf("%d%d",&src[i].x,&src[i].y);
        int num = graphm(src,N);
        if (num < N) {
            printf("I can‘t cut.\n");
        }
        else {
            memset(cost,0,sizeof(cost));
            for (int i = 0 ; i < N ; i++) {
                for (int j = i + 2 ; j < N ; j++) cost[i][j] = cost[j][i] = getcost(save[i],save[j]);
            }
            memset(dp,0x3f,sizeof(dp));
            for (int i = 0 ; i < N ; i++) dp[i][(i + 1) % N] = 0;
            for (int d = 2 ; d <= N ; d++) {
                for (int i = 0 ; i + d - 1 < N ; i++) {
                    int j = d + i - 1;
                    for (int k = i + 1; k < j ; k++)
                        dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j] + cost[i][k] + cost[k][j]);
                }
            }
            printf("%d\n",dp[0][N - 1]);
        }
    }
    return 0;
}