## USACO, Section : 1.4 , Packing Rectangles

Moderator: Board moderators

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### USACO, Section : 1.4 , Packing Rectangles

Code: Select all

``````
Four rectangles are given. Find the smallest enclosing (new) rectangle into which these four may be fitted without overlapping. By smallest rectangle, we mean the one with the smallest area.

All four rectangles should have their sides parallel to the corresponding sides of the enclosing rectangle. Figure 1 shows six ways to fit four rectangles together. These six are the only possible basic layouts, since any other layout can be obtained from a basic layout by rotation or reflection. Rectangles may be rotated 90 degrees during packing.

There may exist several different enclosing rectangles fulfilling the requirements, all with the same area. You must produce all such enclosing rectangles.
PROGRAM NAME: packrec
INPUT FORMAT

Four lines, each containing two positive space-separated integers that represent the lengths of a rectangle's two sides. Each side of a rectangle is at least 1 and at most 50.
SAMPLE INPUT (file packrec.in)

1 2
2 3
3 4
4 5

OUTPUT FORMAT
The output file contains one line more than the number of solutions. The first line contains a single integer: the minimum area of the enclosing rectangles. Each of the following lines contains one solution described by two numbers p and q with p<=q. These lines must be sorted in ascending order of p, and must all be different.
SAMPLE OUTPUT (file packrec.out)

40
4 10
5 8

``````
can anyone please shed some light on this problem? i am very weak at geometry so can anyone please help me solving this problem.

my idea is to check all possible orientation but as im weak in geometry, Im missing the geometry part.

HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
i did a brute force over all possible rectangle combinations(consider rotating a rectangle too) and checked it with the 6 layouts given(actually 5 as layout 4,5 are same).

but be careful when checking the 6th layout. not only the bottom 2 rectangles can touch but also the bottom-left & upper-right or the bottom-right & upper-left or the upper 2 rectangles can touch.

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### Help on packing rectangle.........

hello,
thank you for the help. im not good at geometry. so i am not confident about finding the height and width of the different scenarios

case 1 :
1 2 3 4
H = max4(h1,h2,h3,h4); W = w1+w2+w3+w4 ;

case 2:
(1 2 3)
4
H = max3(h1,h2,h3)+h4; W = max2( w4,w1+w2+w3);

case 3 :
( 1 2 ) 4
3
H = max2( h4, max2( h1,h2) + h3 ) ; W = w4 + max2(w1+w2,w3) ;

case 4:
2
1 3 4

H = max3( h1 , h2 + h3 , h4 ) ; W = w1 + max2( w2 , w3 ) + w4 ;

case 5:
1
2 3 4

H = max3( h1+h2,h3,h4) ; W = max2( w1,w2) + w3 + w4 ;

case 6 :

3 4
1 2

H = max2( h1 + h3 , h2 + h4 ) ;
if( h1<=h2) W = max2( w1 + w2 , w3 + w4 ) ;
else W = max2( w1,w3) + max2( w2,w4);

HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

i forgot to give the picture of the 6 basic layouts. i wrote all the formulas in one of my previous post. could some one check those and tell me weither my formulas are correct or not. i will remove all my post as soon as i get accepted in this problem.
bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I sent you a PM

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
thanx man. you are a great helper
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

looserdgr8
New poster
Posts: 5
Joined: Sun Aug 23, 2009 2:07 am
Location: Sust, Sylhet

### Re: USACO, Section : 1.4 , Packing Rectangles

can anyone give me any idea of that problem..... ??