Packing Rectangles - nazgul's Blog
Packing Rectangles
nazgul
posted @ 2011年2月26日 06:16
in USACO
, 1002 阅读
题目大意:有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; }