Packing Rectangles - USACO 1.4.1

packingrectangles - codetrick
our rectangles are given. Find the smallest enclosing (new) rectangle into which these four may be fitted without overlapping. By smallest rectangle, we mean the one with the smallest area.
All four rectangles should have their sides parallel to the corresponding sides of the enclosing rectangle. Figure 1 shows six ways to fit four rectangles together. These six are the only possible basic layouts, since any other layout can be obtained from a basic layout by rotation or reflection. Rectangles may be rotated 90 degrees during packing.
There may exist several different enclosing rectangles fulfilling the requirements, all with the same area. You must produce all such enclosing rectangles.

PROGRAM NAME: packrec

INPUT FORMAT

Four lines, each containing two positive space-separated integers that represent the lengths of a rectangle's two sides. Each side of a rectangle is at least 1 and at most 50.

SAMPLE INPUT (file packrec.in)

1 2  2 3  3 4  4 5  

OUTPUT FORMAT

The output file contains one line more than the number of solutions. The first line contains a single integer: the minimum area of the enclosing rectangles. Each of the following lines contains one solution described by two numbers p and q with p<=q. These lines must be sorted in ascending order of p, and must all be different.

SAMPLE OUTPUT (file packrec.out)

40  

4 10  5 8

http://leonlu.iteye.com/blog/1124549

http://starforever.blog.hexun.com/2097115_d.html

因为只有4个方块，所以枚举每个方块的选择顺序和放置方向（横放还是纵放），放置方式只有题目给出的6中基本模式，分别算出不同模式下最小的面积，更新最优解。

第4、5个在本质上其实是一样。如图，不同模式对应的最小面积如下：

设w1,w2,w3,w4表示4个方块的横长，h1,h2,h3,h4表示4个方块的纵长。w,h表示最小。

1：w=w1+w2+w3+w4；h=max(h1,h2,h3,h4)

2：w=max(w1+w2+w3,w4)；h=max(h1,h2,h3)+h4

3：w=max(w1+w2,w3)+w4；h=max(h1+h3,h2+h3,h4)

4：w=w1+w2+max(w3,w4)；h=max(h1,h3+h4,h2)

5：h=max(h1+h3,h2+h4)

对于w，我们细分为如下四种形式：

(1)：h3>=h2+h4；w=max(w1,w3+w2,w3+w4)

(2)：h3>h4 and h3<h2+h4；w=max(w1+w2,w2+w3,w3+w4)

(3)：h4>h3 and h4<h1+h3；w=max(w1+w2,w1+w4,w3+w4)

(4)：h4>=h1+h3；w=max(w2,w1+w4,w3+w4)

*：h3=h4（图中没画）；w=max(w1+w2,w3+w4)

用一个数组记录最优解，最后排序输出即可。

子集树：遍历子集树需要O（n^2）的时间 

Java代码  

1. void backtrack (int t){  
2.     if (t>n) output(X); // X是最终解  
3.     else{  
4.         X[t]=true;  
5.         if (legal(t)) backtrack (t+1); // X是部分解  
6.         X[t]= false;  
7.         if (legal(t)) backtrack (t+1); // X是部分解  
8.     }  
9. }  

排列树：遍历排列树需要O（n!）的时间 

Java代码  

1. void backtrack  (int t)  
2. {  
3.     if (t>n) output(X);  // X是最终解  
4.     else  
5.         for (int i=t;i<=n;i++) {  
6.         swap(x[t], x[i]);  
7.         if (legal(t)) backtrack(t+1); // X是部分解  
8.         swap(x[t], x[i]);  
9.     }  
10. }   

https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/packrec.java

	// possible solutions: 4! * 2^4 * 5 = 1920 public class packrec {
	private static List<Rectangle> results = new ArrayList<Rectangle>();
	public static void main(String[] args) throws IOException {
	BufferedReader in = new BufferedReader(new FileReader("packrec.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
	"packrec.out")),true);
	// read in
	Rectangle[] recs = new Rectangle[4];
	for(int i = 0; i < 4; i++){
	StringTokenizer st = new StringTokenizer(in.readLine());
	recs[i] = new Rectangle(Integer.parseInt(st.nextToken()),
	Integer.parseInt(st.nextToken()));
	}
	// backtrack with permutation and subset
	permutate(0,recs);
	// sort by area and w
	Collections.sort(results, new Comparator<Rectangle>(){
	public int compare(Rectangle arg0, Rectangle arg1) {
	if(arg0.size() < arg1.size()) return -1;
	if(arg0.size() > arg1.size()) return 1;
	if(arg0.w < arg1.w) return -1;
	if(arg0.w > arg1.w) return 1;
	return 0;
	}});
	// output
	int size = results.get(0).size();
	out.println(size);
	int w = results.get(0).w;
	int h = results.get(0).h;
	out.println(w + " " + h);
	for(int i = 1; i < results.size(); i ++){
	Rectangle r = results.get(i);
	if(r.size() != size)
	break;
	if(r.w == w && r.h == h)
	continue;
	out.println(r.w + " " + r.h);
	w = r.w;
	h = r.h;
	}
	System.exit(0);
	}
	private static Rectangle[] calculate(int w1, int w2, int w3, int w4,
	int h1, int h2, int h3, int h4){
	Rectangle[] a = new Rectangle[5];
	//1:
	int width = w1 + w2 + w3 + w4;
	int height = max(max(h1, h2),max(h3, h4));
	a[0] = new Rectangle(width, height);
	//2:
	height = w1 + max(max(h2, h3),h4);
	width = max(h1, w2 + w3 + w4);
	a[1] = new Rectangle(width, height);
	//3:
	height = max(h1, w2 + max(h3, h4));
	width = w1 + max(h2, w3 + w4);
	a[2] = new Rectangle(width, height);
	//4,5:
	width = max(w2,w4) + w1 + w3;
	height= max(max(h1, h3),h2 + h4);
	a[3] = new Rectangle(width, height);
	//6
	height = max(h1+h3, h2+h4);
	if(h3 >= h2 + h4)
	width = max(w1, max(w3+w2,w3+w4));
	else if (h3 > h4 && h3 < h2+h4)
	width = max(max(w1+w2, w2+w3),w3+w4);
	else if( h3 < h4 && h4 < h1+h3)
	width = max(max(w1+w2, w1+w4), w3+w4);
	else if (h4 >=h1+h3)
	width = max(max(w1+w4, w3+w4), w2);
	else // h4 == h3
	width = max(w1+w2, w3+w4);
	a[4] = new Rectangle(width,height);
	return a;
	}
	// length!
	private static void permutate(int t, Rectangle[] recs){
	if(t == recs.length)
	subset(0,recs);// subset
	else
	for(int i = t; i < recs.length; i++){
	swap(recs,t,i);
	permutate(t+1,recs);
	swap(recs,t,i);
	}
	}
	private static void swap(Rectangle[] a, int p1, int p2){
	Rectangle tmp = a[p1];
	a[p1] = a[p2];
	a[p2] = tmp;
	}
	// 2^length
	private static void subset(int t, Rectangle[] recs){
	if(t == recs.length)
	Collections.addAll(results,calculate(recs[0].w,recs[1].w,recs[2].w,recs[3].w,
	recs[0].h,recs[1].h,recs[2].h,recs[3].h));
	else{
	// do not exchange h with w
	subset(t+1,recs);
	// exchange h with w
	int tmp = recs[t].h; recs[t].h = recs[t].w; recs[t].w = tmp;
	subset(t+1,recs);
	}
	}
	}
	class Rectangle{
	public int h;
	public int w;
	public Rectangle(int x, int y){
	w = (x < y ? x : y);
	h = (x > y ? x : y);
	}
	public int size(){
	return h * w;
	}
	}

这题有很多贪心的写法
Read full article from packingrectangles - codetrick