USACO, Section : 1.4 , Packing Rectangles

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

USACO, Section : 1.4 , Packing Rectangles

Post by Riyad »

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.


thanx in advance
Riyad
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

Post by sunny »

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.

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

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

Post by Riyad »

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);

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

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

Post by Riyad »

any one please help me with this problem. i am still stuck in this section. please help.thanx in advance
bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

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

Post by Riyad »

Image
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
Riyad [/img]
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

Post by little joey »

I sent you a PM

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

Post by Riyad »

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

Post by looserdgr8 »

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

Post Reply

Return to “Algorithms”