USACO/packrec

Translate:USACO/packrec

Packing Rectangles 铺放矩形块 (IOI 95)

[编辑]描述

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

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

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

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

编辑]

格式

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

SAMPLE INPUT

1 22 33 44 5

[编辑]SAMPLE OUTPUT

404 105 8

/*ID: liluvu1LANG: C++TASK: packrec*/#include <stdio.h>#include <string.h>#include <stdlib.h>#define N 4#define M 200typedef 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;}