区间dp+判断凸包

Cake
You want to hold a party. Here’s a polygon-shaped cake on the table. You’d like to cut the cake into several triangle-shaped parts for the invited comers. You have a knife to cut. The trace of each cut is a line segment, whose two endpoints are two vertices of the polygon. Within the polygon, any two cuts ought to be disjoint. Of course, the situation that only the endpoints of two segments intersect is allowed.

The cake’s considered as a coordinate system. You have known the coordinates of vexteces. Each cut has a cost related to the coordinate of the vertex, whose formula is $c o s t_{i, j} = ∣ x_{i} + x_{j} ∣ * ∣ y_{i} + y_{j} ∣$ . You want to calculate the minimum cost.

NOTICE: input assures that NO three adjacent vertices on the polygon-shaped cake are in a line. And the cake is not always a convex.

Input
There’re multiple cases. There’s a blank line between two cases. The first line of each case contains two integers, N and p (3 ≤ N, p ≤ 300), indicating the number of vertices. Each line of the following N lines contains two integers, x and y (-10000 ≤ x, y ≤ 10000), indicating the coordinate of a vertex. You have known that no two vertices are in the same coordinate.

Output
If the cake is not convex polygon-shaped, output “I can’t cut.”. Otherwise, output the minimum cost.

Sample Input

Sample Output

#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define Init(arr,val) memset(arr,val,sizeof(arr))
#define lowbit(x) ((x)&(-x))
#define lson (i<<1),l,mid
#define rson (i<<1|1),mid+1,r
#define mid ((l+r)>>1)
typedef unsigned long long ll;
const int inf=0x3f3f3f3f,mod=1000000007,MAXN=400;
struct pt{
    int x,y;
}k[MAXN];
bool cross(const pt&a,const pt&b,const pt&z){//a*b
    return (a.x-z.x)*(b.y-z.y)-(a.y-z.y)*(b.x-z.x)>=0;
}
bool cmp(const pt&a,const pt&b){return cross(a,b,k[0]);}
int ans[MAXN],num,n,p;
bool graham(){
    int cnt=0;
    for(int i=1;i<n;++i)if((k[cnt].y>k[i].y)||(k[cnt].y==k[i].y&&k[cnt].x>k[i].x))cnt=i;
    swap(k[0],k[cnt]);
    sort(k+1,k+n,cmp);
    ans[0]=0;
    ans[1]=num=1;
    for(int i=2;i<n;++i){
        if(num>1&&!cross(k[ans[num]],k[i],k[ans[num-1]]))return 0;
        //如果要出栈，n个点肯定不能全组成凸包
        ans[++num]=i;
    }
    return 1;
}
int cost[MAXN][MAXN],dp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dfs(int x,int y){//直接dfs好写点
    if(abs(x-y)<3)return 0;//构不成或刚好构成三角，花费=0
    if(vis[x][y])return dp[x][y];//判断过
    for(int k=x+1;k<y;++k)
        dp[x][y]=min(dp[x][y],dfs(x,k)+dfs(k,y)+cost[x][k]+cost[k][y]);
    vis[x][y]=1;
    return dp[x][y];
}
int main(){
    while(~scanf("%d%d",&n,&p)){
        for(int i=0;i<n;++i)scanf("%d%d",&k[i].x,&k[i].y);
        if(!graham()){printf("I can't cut.\n");continue;}
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(i==j||abs(i-j)==1||abs(i-j)==n-1)continue;
                cost[i][j]=abs((k[i].x+k[j].x)*(k[i].y+k[j].y))%p;
            }
        }
        Init(dp,inf);
        Init(vis,0);
        printf("%d\n",dfs(0,n-1));
    }
    return 0;
}