当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ1082铺放矩形块[USACO]
1943+

题目大意:4个矩形,怎么放才能用一个更小的矩形框把他们框住?最小的矩形框面积是多少?长和宽分别是多少?

题目描述

给定4个矩形块,找出一个最小的封闭矩形将这4个矩形块放入,但不得相互重叠。所谓最小矩形指该矩形面积最小。

                                   图1 四个矩形的六个基本布局

4个矩形块中任一个矩形的边都与封闭矩形的边相平行,图1显示出了铺放4个矩形块的6种方案。这6种方案是唯一可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。

可能存在满足条件且有着同样面积的各种不同的封闭矩形,你的程序应该输出所有这些封闭矩形的边长。

输入

共有4行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围最小是1,最大是50。

输出

总行数为解的总数加1。第一行是一个整数,代表封闭矩形的最小面积(子任务A)。接下来的每一行都表示一个解,由数P和数Q来表示,并且P≤Q(子任务B)。这些行必须根据P的大小按升序排列,P小的行在前,大的在后。且所有行都应是不同的。

样例输入

1 2
2 3
3 4
4 5

样例输出

40
4 10
5 8

解题思路

给每一种布局的4个矩形进行编号,暴力枚举每个位置放哪个矩形,包括横着放,即原来的a和b,以及竖着放,即长和宽倒过来的b和a。

枚举好之后,计算各种布局的长和宽,根据长和宽计算面积,如果面积是最小值,那么标记一下f[0]和f[i]为最小面积,已确定最小面积以及面积最小时长/宽是i。

计算面积,需要分类讨论:

布局1:长是4个矩形的长之和;宽是4个矩形的宽的最大值。

布局2:长是前3个矩形长之和跟第4个矩形长的最大值;宽是前3个矩形的宽的最大值加上第4个矩形的宽。

布局3:(从左到右编号,下面横着的是4号)长是第4个的长加上左边的最大值;宽是左右两边宽的最大值,左边还要嵌套求最大值。

布局4和5:上下两个编号成3和4,那么放中间还是左边结果是相同的,求法类似。

布局6:代码23行,规定上面两个的长要比下面两个的小,因为如果大的话,就是旋转,也会求到的,限制了之后后面更好分类讨论。

首先编号,右下角为1号,顺时针依次编号,宽肯定是左边宽和右边宽的最大值,上面两个不会给顶上去,因为不够长;

接着是长,至少是下面两个的长之和,但中间可能有空隙,如3比2长且1比2要宽、4比1长且2比1要宽。

(f数组开200,因为边长最长是50*4=200)

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

SSOJ1082铺放矩形块[USACO]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!