Packing Rectangles - nazgul's Blog

Packing Rectangles

nazgul posted @ 2011年2月26日 06:16 in USACO , 999 阅读

题目大意:有4个长方形,放在一起,不能重叠,然后用一个长方形包围,这个长方形的面积最小为多少,宽度和长度为多少。如果有多组长宽都符合最小的话,那么按照p从大到小输出。

题目中提示只有题中给的6种情况,其他的情况都可以由这6种经过旋转,映像得到。

分析:题目中的6种中4和5其实是一种,旋转和映像得到的长方形应该和不经过旋转是一样的,所以只有5种情况。解题思想就是枚举每一种放置的顺序,然后进行判断,找到最小的面积。对于最后一种情况应该要根据4个长方形的长宽进行分类,具体见代码。

 

/*
ID: nazgul12
LANG: C
TASK: packrec
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct{ int x, y; } st;

st s[4], xy, sol[100];
int e[4], used[4] = {0};
int mini = 0x7fffffff, l;

void swap( st * t )
{
	int temp;
	temp = t->x; t->x = t->y; t->y = temp;
}

int mmax( int a, int b )
{
	return a > b ? a : b;
}

int sum( int l, int r )
{
	int t = 0, i;
	for ( i = l; i <= r; ++i )
		t += s[e[i]].x;
	return t;
}

int max( int l, int r )
{
	int t = 0, i;
	for ( i = l; i <= r; ++i )
		if ( s[e[i]].y > t )
			t = s[e[i]].y;
	return t;
}

void solve()
{
	int i;
	if ( xy.x > xy.y ) swap( &xy );
	if ( xy.x * xy.y > mini ) return;
	if ( xy.x * xy.y < mini )
	{
		l = 0; mini = xy.x * xy.y;
	}
	if ( xy.x * xy.y == mini )
	{
		for ( i = 0; i < l; ++i )
			if ( xy.x == sol[i].x )
				return;
	}
	sol[l].x = xy.x; sol[l].y = xy.y;
	l++;
}

void test()
{
	xy.x = sum( 0, 3 ); xy.y = max( 0, 3 );
	solve();
	xy.x = mmax( s[e[0]].x, sum( 1, 3 ) );
	xy.y = max( 1, 3 ) + s[e[0]].y;
	solve();
	xy.x = mmax( s[e[0]].x, sum( 1, 2 ) ) + s[e[3]].x;
	xy.y = mmax( s[e[3]].y, mmax( s[e[1]].y, s[e[2]].y ) + s[e[0]].y );
	solve();
	xy.x = mmax( s[e[1]].x, s[e[2]].x ) + s[e[0]].x + s[e[3]].x;
	xy.y = mmax( mmax( s[e[0]].y, s[e[3]].y ), s[e[1]].y + s[e[2]].y );
	solve();
	if ( s[e[1]].y <= s[e[0]].y && s[e[1]].x >= s[e[2]].x &&
		s[e[0]].x <= s[e[3]].x && s[e[3]].y <= s[e[2]].y )
		{
			xy.x = mmax( s[e[0]].x+s[e[1]].x , s[e[2]].x+s[e[3]].x );
			xy.y = mmax( s[e[0]].y+s[e[3]].y , s[e[1]].y+s[e[2]].y );
			solve();
		}
	if ( s[e[0]].x <= s[e[1]].x && s[e[2]].x <= s[e[3]].x )
	{
		xy.x = s[e[1]].x + s[e[3]].x;
		xy.y = mmax( s[e[0]].y+s[e[1]].y, s[e[2]].y+s[e[3]].y );
		solve();
	}
}

void dfs( int k )
{
	int i;
	if ( k == 4 ) test();
	else
	{
		for ( i = 0; i < 4; ++i )
			if ( used[i] == 0 )
			{
				e[k] = i; used[i] = 1;
				dfs( k + 1 );
				swap( s+i );
				dfs( k + 1 );
				swap( s+i );
				used[i] = 0;
			}
	}
}

int cmp( const void *a, const void *b )
{
	return ( ( st * )a )->x - ( ( st * )b )->x;
}

int main()
{
	int i;
	freopen( "packrec.in", "r", stdin );
	freopen( "packrec.out", "w", stdout );
	for ( i = 0; i < 4; ++i )
		scanf( "%d%d", &s[i].x, &s[i].y );
	dfs( 0 );
	printf( "%d\n", mini );
	qsort( sol, l, sizeof( sol[0] ), cmp );
	for ( i = 0; i < l; ++i )
		printf( "%d %d\n", sol[i].x, sol[i].y );
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee