USACO, Section : 1.4 , Packing Rectangles

[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

[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.

[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

[Riyad]

any one please help me with this problem. i am still stuck in this section. please help.thanx in advance
bye
Riyad

[Riyad]

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]

[little joey]

I sent you a PM

[Riyad]

thanx man. you are a great helper

[looserdgr8]

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