Cake(볼륨+구간dp)

Description
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 costi, j = |xi + xj| * |yi + yj| % p. 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
3 3 0 0 1 1 0 2
Sample Output
0
제목:
다각형 케이크 한 조각은 모두 삼각형으로 썰어야 하며, 임의의 cut는 두 부분으로 효과적으로 나누어야 한다. cut의 대가cost[i][j]=|xi+xj||||||||yi+yj|%p c o st[i][j] = | x i + x j | | y i + y j |% p, 최소 대가를 묻는다.
분석:
임의로 두 점을 선택하여cut를 하는 것은 모두 유효하기 때문에 다각형은 반드시 볼록 다각형이어야 한다.
dp[i][j]dp[i][j]는 제i개 점에서 제j개 점으로 구성된 다각형 절단의 최소 대가로 (i+1)→(i+1)(i+1)→(j-41) 중 하나를 선택하여 분할할 수 있음을 나타낸다. (i,k,j)(i,k,j)는 삼각형을 형성하고 원래의 기초(i,k)(i,k)(i,k)(k,j)(k,j)연변(cut)을 형성한다.전이 방정식이 있다
dp[i][j]=min{dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]} d p [ i ] [ j ] = m i n { d p [ i ] [ k ] + d p [ k ] [ j ] + c o s t [ i ] [ k ] + c o s t [ k ] [ j ] }
참고: 볼록 다각형에는 인접한 두 점 자체에 모서리가 있으므로 컷할 필요가 없습니다.
코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define bll long long

const int maxn = 330;
const int inf = 1e9+7;
struct point
{
    int x,y;
}p[maxn];
int n,mod,cost[maxn][maxn],dp[maxn][maxn];

int det(point a,point b,point c)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

bool cmp(point a,point b)
{
    return det(a,b,p[0]) > 0;
}

bool graham()
{
    point sta[maxn];
    int u = 0,cnt = 0;
    for (int i=1;iif (p[i].y < p[u].y || (p[i].y == p[u].y && p[i].x < p[u].x))
            u = i;
    swap(p[0],p[u]);
    sort(p+1,p+n,cmp);
    p[n] = p[0];

    for (int i=0;i<2;i++) sta[cnt++] = p[i];
    for (int i=2;i<=n;i++)
    {
        if (det(sta[cnt-1],p[i],sta[cnt-2]) > 0)
            sta[cnt++] = p[i];
        else
            return 0;
    }
    return 1;
}

/*----------------------- dp ---------------------------*/
int solve(int i,int j)
{
    if (j <= i+2) return 0;
    if (dp[i][j] != inf) return dp[i][j];
    for (int k=i+1;kreturn dp[i][j];
}

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

void init()
{
    for (int i=0;ifor (int j=i+1;jfor (int i=0;ifor (int j=i+2;jreturn;
}

int main()
{
    while (scanf("%d %d",&n,&mod)!=EOF)
    {
        for (int i=0;iscanf("%d %d",&p[i].x,&p[i].y);
        if (!graham()) printf("I can't cut.
");
        else
        {
            init();
            printf("%d
",solve(0,n-1));
        }
    }
    return 0;
}