首页 技术 正文
技术 2022年11月23日
0 收藏 350 点赞 2,631 浏览 2658 个字

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

#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;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141815.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:877 阅读:6,227
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:4,051
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:566 阅读:4,853
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:732 阅读:4,786
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:5,876
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,569
助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站