ZOJ - 3537 Cake 凸包+區間DP

傳送門

Cake Time Limit: 1 Second       Memory Limit: 32768 KB

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

題意：先判斷這些點組成的圖形是不是一個凸包，如果不是就輸出I can't cut. 否則就進行如下計算。

把這些凸包要全部分成三角形。也就是要連n-3條邊，并且每切一刀(添一條邊有一個花費的計算。|xi+xj|*|yi+yj|%p，

輸出最小的花費。

idea:都說了最小的花費了，肯定是用DP先局部找最優解，最後輸出最小值。

dp方程 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]);

#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <cstring>
#include <queue>
#include <list>
#include <stdio.h>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <sstream>
#include <functional>
#include <stdlib.h>
#include <time.h>
#include <bitset>
using namespace std;
#define LL long long
#define me(x,y) memset(x,y,sizeof(x));
#define bug printf("***********\n")
using namespace std;
const int mod=1e9+7;
const int maxn=1e4+7;
const int maxx=1e3+100;
const int INF=1<<30;

int n,t,cost[maxx][maxx],dp[maxx][maxx];
struct node
{
    int x,y;
}p[maxn],P[maxn];// p[] 存點 P[] 存凸包
int tot;//tot 凸包的點
int X(node A,node B,node C)//差積 是否<0
{
    return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}

double len(node A,node B)//距離
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

bool cmp(node A,node B)
{
    double pp=X(p[0],A,B);
    if(pp>0)  return 1;
    if(pp<0)  return 0;
    return len(p[0],A)<len(p[0],B); //如果等于0 判斷距離  傳回小的
}
int main()
{
    while(cin>>n>>t)
    {
        for(int i=0;i<n;i++)
            cin>>p[i].x>>p[i].y;
        if(n<=2)
        {
            printf("I can't cut.\n");
            continue;
        }
        else
        {
             for(int i=0;i<n;i++)
            {
                if(p[i].y<p[0].y)  swap(p[i],p[0]);//找出 y軸最小的點
                else if(p[i].y==p[0].y&&p[i].x<p[0].x)  swap(p[i],p[0]);//x坐标小的
            }
            sort(p+1,p+n,cmp);
            P[0]=p[0];
            P[1]=p[1];
            tot=1;
            for(int i=2;i<n;i++)
            {
                while(tot>0&&X(P[tot-1],P[tot],p[i])<=0) tot--;// P[tot-1]上一個點
                tot++;
                P[tot]=p[i];//存入凸包
            }
            tot++;
            if(tot!=n)
            {
                printf("I can't cut.\n");
                continue;
            }
            else
            {
                me(cost,0);
                for(int i=0;i<n;i++)
                    for(int j=i+2;j<n;j++)
                    {
                        if(i==j) continue;
                        cost[i][j]=cost[j][i]=(int)fabs(p[i].x+p[j].x)
                        *(int)fabs(p[i].y+p[j].y)%t;
                    }
                for (int i = 0; i < n; ++i)
                {
                    for (int j = 0; j < n; ++j)
                        dp[i][j] = INF;
                }
                for (int i = n - 3; i >= 0; i--)
                    for (int j = i + 2; j < n; j++)
                        for (int k = i + 1; k <= j - 1; 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]);
            }
        }
    }
}