HBC20237[SCOI2003]切割多边形题解

原来我爱你 算法基础篇 54 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
有一个凸p边形,我们希望通过切割得到它,一开始的时候,你有一个n*m的矩形,即它的四角的坐标分 别为(0,0), (0,m), (n,0), (n,m), 每次你可以选择一条直线把当前图形切割成两部分,保留其中一个部分切割线的长度为此直线在多边形内部的部分的长度, 求出最短的切割线总长度,下面是一个例子,我们 需要得到中间的多边形, 分别沿着直线1,2,3,4进行切割即可,得到中间的四边形。

有一个凸p边形(p ≤ 8),我们希望通过切割得到它。一开始的时候,你有一个n*m的矩形,即它的四角的坐标分 别为(0,0), (0,m), (n,0), (n,m)。 每次你可以选择一条直线把当前图形切割成两部分,保留其中一个部分(另一 部分扔掉)切割线的长度为此直线在多边形内部的部分的长度。 求出最短的切割线总长度。下面是一个例子。我们 需要得到中间的多边形。   分别沿着直线1,2,3,4进行切割即可,得到中间的四边形。

HBC20237[SCOI2003]切割多边形题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)

标签: HBC20237[SCOI2003]切割多边形题解