首页 > 代码库 > bzoj1091: [SCOI2003]切割多边形
bzoj1091: [SCOI2003]切割多边形
Description
有一个凸p边形(p<=8)，我们希望通过切割得到它。一开始的时候，你有一个n*m的矩形，即它的四角的坐标分
别为(0,0), (0,m), (n,0), (n,m)。每次你可以选择一条直线把当前图形切割成两部分，保留其中一个部分（另一
部分扔掉）切割线的长度为此直线在多边形内部的部分的长度。求出最短的切割线总长度。下面是一个例子。我们
需要得到中间的多边形。
分别沿着直线1，2，3，4进行切割即可，得到中间的四边形。
Input
第一行有两个整数n, m(0 < n,m < 500)，第二行为一个整数p(3<=p<=8)。以下p行每行为两个整数x, y(0 < x
< n, 0 < y < m)，为按顺时针给出的各顶点坐标。数据保证多边形的是凸的，无三点共线。输入数据无错误。
Output
仅一行，为最短切割线的总长度，四舍五入到小数点后3位。允许有0.001的误差。
枚举切割顺序，然后模拟加入直线，暴力计算与其余直线的交点
#include<cstdio>#include<cmath>#include<algorithm>int n,id[11],lp=0;double v1,v2,ans=1e10;struct pos{ double x,y; void init(){scanf("%lf%lf",&x,&y);} pos operator+(pos a){return (pos){x+a.x,y+a.y};} pos operator-(pos a){return (pos){x-a.x,y-a.y};} pos operator*(double a){return (pos){x*a,y*a};} double operator*(pos a){return x*a.y-y*a.x;} double dot(pos a){return x*a.x+y*a.y;} double abs(){return sqrt(x*x+y*y);}}ps[11];double mn,mx;struct line{ pos a,b; void chk(line w){ double c=w.b*b; if(c==0)return; c=(a*w.b+w.b*w.a)/c; if(c>0.5)c<mx&&(mx=c); else c>mn&&(mn=c); }}ls[15],l0[11];int main(){ scanf("%lf%lf%d",&v1,&v2,&n); for(int i=1;i<=n;++i)ps[i].init(),id[i]=i; ps[n+1]=ps[1]; pos p1=(pos){0,0},p2=(pos){v1,0},p3=(pos){v1,v2},p4=(pos){0,v2}; ls[lp++]=(line){p1,p2-p1}; ls[lp++]=(line){p2,p3-p2}; ls[lp++]=(line){p3,p4-p3}; ls[lp++]=(line){p4,p1-p4}; for(int i=1;i<=n;++i)l0[i]=(line){ps[i],ps[i+1]-ps[i]}; do{ lp=4; double s=0; for(int i=1;i<=n;++i){ int w=id[i]; mn=-1e10,mx=1e10; for(int j=0;j<lp;++j)l0[w].chk(ls[j]); ls[lp++]=l0[w]; s+=(mx-mn)*l0[w].b.abs(); } if(s<ans)ans=s; }while(std::next_permutation(id+1,id+n+1)); printf("%.3f",ans); return 0;}
bzoj1091: [SCOI2003]切割多边形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。