#USACO1013. 1.4.1 铺放矩形块 Packing Rectangles

1.4.1 铺放矩形块 Packing Rectangles

题目描述

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

44 个矩形块中任一个矩形的边都与封闭矩形的边相平行,上图显示出了铺放 44 个矩形块的 66 种方案。

66 种方案是唯一可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。

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

输入格式

共有 44 行,每行两个正整数,表示每个矩形的边长。

输出格式

总行数为解的总数加一。

第一行是一个整数,代表封闭矩形的最小面积。
接下来的每一行都表示一个解,由 p,q (pq)p,q\space (p \leqslant q) 来表示。这些行必须根据 pp 的大小按升序排列,且所有行都应是不同的。

样例 #1

样例输入 #1

1 2
2 3
3 4
4 5

样例输出 #1

40
4 10
5 8

提示

【数据范围】
对于 100%100\% 的数据,输入的所有数在 [1,50][1,50] 内。

题目翻译来自NOCOW。

USACO Training Section 1.4