栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3537 Cake

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3537 Cake

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define eps 1e-8#define inf 0x7ffffffusing namespace std;struct Tpoint{int x,y;void in(){scanf("%d%d",&x,&y);}}p[400],hull[400];int dis(Tpoint a,Tpoint b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}int cross(Tpoint a,Tpoint b,Tpoint c){return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}bool gra_cmp(Tpoint b,Tpoint c){double tmp=cross(b,c,p[0]);if(tmp>eps)return true;if(fabs(tmp)<eps&&dis(b,p[0])<dis(c,p[0]))return true;return false;}int graham_scan(Tpoint hull[],int n){int top,i,k=0;for(i=1;i<n;i++)if((p[k].y-p[i].y)>eps||fabs(p[k].y-p[i].y)<eps&&p[k].x-p[i].x>eps)k=i;swap(p[0],p[k]);sort(p+1,p+n,gra_cmp);hull[0]=p[0];hull[1]=p[1];hull[2]=p[2];if(n<3)return n;else top=3;for(i=3;i<n;i++){while(top>=2&&cross(hull[top-2],hull[top-1],p[i])<eps)top--;hull[top++]=p[i];}return top;}int gao(Tpoint a,Tpoint b,int p){return (abs(a.x+b.x)*abs(a.y+b.y))%p;}int cost[305][305],d[305][305];int main(){int tmp,i,j,k,n,m,Mod;while(scanf("%d%d",&n,&Mod)!=EOF){for(i=0;i<n;i++)p[i].in();tmp=graham_scan(hull,n);if(tmp<n){printf("I can't cut.n");continue;}memset(cost,0,sizeof(cost));for(i=0;i<n;i++)for(j=i+2;j<n;j++){cost[i][j]=cost[j][i]=gao(p[i],p[j],Mod);}cost[0][n-1]=cost[n-1][0]=0;for(i=0;i<n;i++)for(j=0;j<n;j++){d[i][j]=inf;}for(i=0;i<n;i++)d[i][(i+1)%n]=0;for(i=n-2;i>=0;i--){for(j=i+2;j<n;j++){for(k=i+1;k<j;k++){if(d[i][k]+d[k][j]+cost[i][j]<d[i][j])d[i][j]=d[i][k]+d[k][j]+cost[i][j];}}}printf("%dn",d[0][n-1]);}}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/380126.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号