USACO - 1.4.1 - Packing Rectangles

 

原创文章转载请注明出处

摘要：模拟

一. 题目翻译

1. 描述：

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

          

图一

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

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

2. 格式：

          INPUT FORMAT:

           (file packrec.in)

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

          OUTPUT FORMAT:

          (file packrec.out)

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

3. SAMPLE：

          SAMPLE INPUT:

1 2

2 3

3 4

4 5

          SAMPLE OUTPUT:

40

4 10

5 8

4. 样例分析：

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          非常恶心的一道枚举题目，我是参考如下说明的，从这里转载的http://starforever.blog.hexun.com/2097115_d.html。大家直接参考里面的说明吧 。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:packrec
*/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class packrec {

	public static void main(String[] args) {
		try {
			Scanner in = new Scanner (new BufferedReader(new FileReader("packrec.in")));
			PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("packrec.out")));
			
			LinkedList<Node> ll = new LinkedList<Node>();
			while (in.hasNextLine()){
				StringTokenizer tokens = new StringTokenizer(in.nextLine());
				int x = Integer.parseInt(tokens.nextToken());
				int y = Integer.parseInt(tokens.nextToken());
				ll.add(new Node(x, y));
			}
			
			Max max = new Max(100000);
			LinkedList<Node> templl = new LinkedList<Node>();
			dfs(ll, templl, max);
			
			pw.println(max.maxArea);
			for (int i=0;i<max.ll.size();i++){
				pw.println(max.ll.get(i).length+" "+max.ll.get(i).height);
			}
			pw.close();
			in.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static void dfs(LinkedList<Node> ll,LinkedList<Node> templl,Max max){
		if (ll.size()==0){
			doPack(templl.get(0), templl.get(1), templl.get(2), templl.get(3), max);
		} else {
			for (int i=0;i<ll.size();i++){
				Node temp = ll.removeFirst();
				templl.addLast(new Node(temp.height,temp.length));
				dfs(ll, templl, max);
				templl.removeLast();
				templl.addLast(new Node(temp.length,temp.height));
				dfs(ll,templl,max);
				templl.removeLast();
				ll.addLast(temp);
			}
		}
	}
	
	public static void doPack(Node node1,Node node2,Node node3,Node node4,Max max){
		int length = node1.length + node2.length + node3.length + node4.length;
		int height = max(max(node1.height,node2.height,-1),node3.height,node4.height);
		if (length*height<max.maxArea){
			max.newMax(length*height, length, height);
		} else if(length*height == max.maxArea){
			max.addNode(length, height);
		}
		
		length = max(node1.length+node2.length+node3.length,node4.length,-1);
		height = max(node1.height,node2.height,node3.height)+node4.height;
		if (length*height<max.maxArea){
			max.newMax(length*height, length, height);
		} else if(length*height == max.maxArea){
			max.addNode(length, height);
		}
		
		length = max(node1.length+node2.length+node4.length,node3.length+node4.length,-1);
		height = max(node1.height+node3.height,node2.height+node3.height,node4.height);
		if (length*height < max.maxArea){
			max.newMax(length*height, length, height);
		} else if(length*height == max.maxArea){
			max.addNode(length, height);
		}
		
		length =node1.length+node2.length+max(node3.length,node4.length,-1);
		height = max(node1.height,node3.height+node4.height,node2.height);
		if (length*height<max.maxArea){
			max.newMax(length*height, length, height);
		} else if(length*height == max.maxArea){
			max.addNode(length, height);
		}
		
		height = max (node1.height + node3.height,node2.height+node4.height, -1);
		if(node3.height>=(node2.height+node4.height)){
			length = max(node1.length,node2.length+node3.length,node3.length+node4.length);
		} 
		if (node3.height>node4.height&&node3.height<(node2.height+node4.height)){
			length = max(node1.length+node2.length,node2.length+node3.length,node3.length+node4.length);
		}
		if (node4.height>node3.height&&node4.height<(node1.height+node3.height)){
			length = max(node1.length+node2.length, node1.length+node4.length, node3.length+node4.length);
		} 
		if (node4.height>=(node1.height+node3.height)){
			length = max(node2.length,node1.length+node4.length,node3.length+node4.length);
		} 
		if (node3.height==node4.height) {
			length = max(node1.length+node2.length,node3.length+node4.length,-1);
		}
		if (length*height<max.maxArea){
			max.newMax(length*height, length, height);
		} else if(length*height == max.maxArea){
			max.addNode(length, height);
		}
	}
	
	public static int max(int i,int j,int k){
		if (i>j){
			if (i>k){
				return i;
			}else {
				return k;
			}
		} else {
			if (j>k){
				return j;
			}else{
				return k;
			}
		}
	}
}

class Node {
	int length;
	int height;
	
	public Node(int x,int y) {
		this.length = x;
		this.height = y;
	}
}

class Max{
	int maxArea ;
	LinkedList<Node> ll;
	
	public Max(int maxArea) {
		this.maxArea = maxArea;
		ll = new LinkedList<Node>();
	}
	
	public void newMax (int maxArea,int length ,int height){
		ll.clear();
		this.maxArea = maxArea;
		if (length<height){
			ll.add(new Node(length, height));
		} else {
			ll.add(new Node(height, length));
		}
	}
	
	public void addNode(int length, int height){
		Node node;
		if (length<height){
			node = new Node(length,height);
		}else {
			node = new Node(height, length);
		}
		int i=0;
		for (;i<ll.size();i++){
			if (node.length<ll.get(i).length){
				ll.add(i,node);
				break;
			} else if (node.length==ll.get(i).length){
				break;
			} else {
				//doNothing
			}
		}
		if (i == ll.size()){
			ll.addLast(node);
		}
	}
}