USACO/packrec

Translate:USACO/packrec

Packing Rectangles 铺放矩形块 (IOI 95)

[编辑]描述

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

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

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

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

编辑]

格式

PROGRAM NAME: packrec

INPUT FORMAT:(file packrec.in)
共有4行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围最小是1，最大是50。

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

SAMPLE INPUT

1 2
2 3
3 4
4 5

[编辑]SAMPLE OUTPUT

40
4 10
5 8

/*
ID: liluvu1
LANG: C++
TASK: packrec
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N 4
#define M 200

typedef struct Rect {
	int w;
	int h;
} Rect;

Rect rect[4];

int maps[M+1][M+1];
int res[M+1];
int ways[N];

int minArea = 40000;

void makeW(int i){
	int t = 0;
	if (rect[i].w < rect[i].h) {
		t = rect[i].w;
		rect[i].w = rect[i].h;
		rect[i].h = t;
	}
}

void makeH(int i){
	int t = 0;
	if (rect[i].w > rect[i].h) {
		t = rect[i].w;
		rect[i].w = rect[i].h;
		rect[i].h = t;
	}
}


int max(int a, int b){
	if (a > b)
		return a;
	else 
		return b;
}

int cal(int lo){
	int w = 0;
	int h = 0;
	switch (lo) {
		case 1:
			w = rect[ways[0]].w + rect[ways[1]].w + rect[ways[2]].w + rect[ways[3]].w;
			h = max(max(max(rect[ways[0]].h, rect[ways[1]].h), rect[ways[2]].h), rect[ways[3]].h);			
			break;		
		
		case 2:
			w = max(rect[ways[0]].w, (rect[ways[1]].w + rect[ways[2]].w + rect[ways[3]].w));
			h = rect[ways[0]].h + max(max(rect[ways[1]].h, rect[ways[2]].h), rect[ways[3]].h);
			break;

		case 3:
			w = max(rect[ways[0]].w, (rect[ways[1]].w + rect[ways[2]].w)) + rect[ways[3]].w;
			h = max(rect[ways[3]].h, rect[ways[0]].h+ max(rect[ways[1]].h, rect[ways[2]].h));
			break;

		case 4:
			w = rect[ways[0]].w + max(rect[ways[1]].w, rect[ways[2]].w) + rect[ways[3]].w;
			h = max(max(rect[ways[0]].h, rect[ways[3]].h), rect[ways[1]].h + rect[ways[2]].h);
			break;

		case 5:
			w = rect[ways[0]].w + max(rect[ways[1]].w, rect[ways[2]].w) + rect[ways[3]].w;
			h = max(max(rect[ways[0]].h, rect[ways[3]].h), rect[ways[1]].h + rect[ways[2]].h);
			break;

		case 6:			
			w = max(rect[ways[2]].w + rect[ways[3]].w, rect[ways[0]].w + rect[ways[1]].w);
			h = max(rect[ways[0]].h + rect[ways[3]].h, rect[ways[1]].h + rect[ways[2]].h);

			if (rect[ways[1]].w > rect[ways[2]].w)
				h = max(h, rect[ways[1]].h + rect[ways[3]].h);

			if (rect[ways[0]].w > rect[ways[3]].w)
				h = max(h, rect[ways[0]].h + rect[ways[2]].h);
			break;	
	}
	maps[w][h] = 1;
	return 1;
}


void rot(int n, int lo){
	if (n == 4){
		cal(lo);
	} else {
		for (int i = 0; i < 2; i++){
			if (i == 0) 
				makeW(n);
			else
				makeH(n);

			rot(n+1, lo);
		}
	}
}


int avail(int n, int v){
	while (n >= 1){
		if (v == ways[n-1])
			return false;
		n--;
	}
	return true;
}

void place(int n, int lo) {
	if (n == 4) {
		rot(0, lo);
	} else {
		for (int i = 0; i < N; i++){
			if (avail(n, i)) {
				ways[n] = i;
				place(n+1, lo);
			}
		}
	}
}

int main(){
	FILE *fin = NULL;
	FILE *fout = NULL;

	fin = fopen("packrec.in", "r");
	fout = fopen("packrec.out", "w");
	
	for (int i = 0; i < N; i++)
		fscanf(fin, "%d %d\n", &rect[i].w, &rect[i].h);

	for (int i = 1; i <= 6; i++){
		memset(ways, 0x0, N*sizeof(int));
		place(0, i);
	}

	for (int i = 1; i <= M; i++){
		for (int j = 1; j <= M; j++){
			if (maps[i][j] && minArea >= i*j) {
				minArea = i*j;						
			}
		}
	}

	fprintf(fout, "%d\n", minArea);	

	for (int i = 1; i <= M; i++){
		for (int j = 1; j <= M; j++){
			if (maps[i][j] && minArea == i*j) {
				res[i] = 1;				
			}
		}
	}

	for (int i = 1; i <= minArea; i++){
		int j = minArea%i;
		if (j == 0) {
			j = minArea/i;
			if ((res[i] || res[j]) && j >= i)
				fprintf(fout, "%d %d\n", i, j);	
		}	
	}	

	return 0;
}