前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >ZOJ 3537 Cake(凸包判定+区间DP)

ZOJ 3537 Cake(凸包判定+区间DP)

作者头像
ShenduCC
发布2018-04-26 14:39:34
6790
发布2018-04-26 14:39:34
举报
文章被收录于专栏:算法修养

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

0

首先得判定一下这些点是否可以构成凸包,只要用凸包算法看看这些点构成的凸包的顶点的个数是否等于n。凸包判定直接参考大牛的博客,模板 http://blog.csdn.net/woshi250hua/article/details/7824433 写区间DP的时候注意循环的顺序

关于区间DP,可以参照这个博客 http://blog.csdn.net/dacc123/article/details/50885903

代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
#define MAX 100000000
int n,p;
struct Node
{
    int x,y;
}a[400];
int s[400];
int cos1[400][400];
int dp[400][400];
int top;
int cross(Node a,Node b,Node c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int dis(Node a,Node b)
{
    return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp(Node p1,Node p2)
{
    int temp=cross(a[0],p1,p2);
    if(temp>0) return true;
    else if(temp==0&&dis(a[0],p1)<dis(a[0],p2)) return true;
    else return false;
}
int graham(int n)
{
    if(n==1){return 0;}
    if(n==2){return 1;}
    if(n>2)
    {
        top=1;s[0]=0;s[1]=1;
        for(int i=2;i<n;i++)
        {
            while(top>0&&cross(a[s[top-1]],a[s[top]],a[i])<=0)
                top--;
            s[++top]=i;
        }
        return top;
    }

}
int cost(Node a,Node b)
{
    return abs(a.x+b.x)*abs(a.y+b.y)%p;
}
int main()
{
    while(scanf("%d%d",&n,&p)!=EOF)
    {
        scanf("%d%d",&a[0].x,&a[0].y);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
            if(a[i].y<a[0].y||(a[i].y==a[0].y&&a[i].x<a[0].x))
            {
                swap(a[i],a[0]);
            }
        }
        sort(a+1,a+n,cmp);
        if(graham(n)!=n-1)
        {
            printf("I can't cut.\n");
            continue;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=i+2;j<n;j++)
                cos1[i][j]=cos1[j][i]=cost(a[i],a[j]);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
                dp[i][j]=MAX;
            dp[i][(i+1)%n]=0;
        }
        for(int i=n-3;i>=0;i--)
        {
            for(int j=i+2;j<n;j++)
            {
                for(int k=i+1;k<j;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+cos1[i][k]+cos1[k][j]);
                }
            }
        }
        printf("%d\n",dp[0][n-1]);
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-03-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档