📄 usaco 1_4_1 packing rectangles 题解_leokan的blog.mht
字号:
href=3D"http://hi.baidu.com/leokan/blog">=B2=A9=BF=CD</A><A=20
href=3D"http://hi.baidu.com/leokan/album">=CF=E0=B2=E1</A><SPAN>|</SPAN><=
A=20
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</A> =
</DIV></DIV>
<DIV class=3Dstage>
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 1.4.1 Packing Rectangles =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C226=C8=D5 =D0=C7=C6=DA=C1=F9 =
11:29</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<CENTER><STRONG><FONT size=3D7>Packing=20
Rectangles</FONT></STRONG><BR><STRONG>IOI 95</STRONG> </CENTER>
<CENTER>
<DIV align=3Dcenter forimg=3D"1"><IMG class=3Dblogimg=20
=
src=3D"http://hiphotos.baidu.com/leokan/pic/item/b9c6c78050a12bd89023d904=
.jpg"=20
border=3D0 small=3D"0"></DIV><BR>The six basic layouts of four =
rectangles=20
</CENTER>
<P>Four rectangles are given. Find the smallest enclosing (new) =
rectangle=20
into which these four may be fitted without overlapping. By =
smallest=20
rectangle, we mean the one with the smallest area.</P>
<P>All four rectangles should have their sides parallel to the=20
corresponding sides of the enclosing rectangle. Figure 1 shows six =
ways to=20
fit four rectangles together. These six are the only possible =
basic=20
layouts, since any other layout can be obtained from a basic =
layout by=20
rotation or reflection. Rectangles may be rotated 90 degrees =
during=20
packing.</P>
<P>There may exist several different enclosing rectangles =
fulfilling the=20
requirements, all with the same area. You must produce all such =
enclosing=20
rectangles.</P>
<H3>PROGRAM NAME: packrec</H3>
<H3>INPUT FORMAT</H3>
<P>Four lines, each containing two positive space-separated =
integers that=20
represent the lengths of a rectangle's two sides. Each side of a =
rectangle=20
is at least 1 and at most 50.</P>
<H3>SAMPLE INPUT (file packrec.in)</H3><PRE>1 2
2 3
3 4
4 5</PRE>
<H3>OUTPUT FORMAT</H3>The output file contains one line more than =
the=20
number of solutions. The first line contains a single integer: the =
minimum=20
area of the enclosing rectangles. Each of the following lines =
contains one=20
solution described by two numbers p and q with p<=3Dq. These =
lines must=20
be sorted in ascending order of p, and must all be different.=20
<H3>SAMPLE OUTPUT (file packrec.out)</H3><PRE>40
4 10
5 8</PRE><PRE> </PRE><PRE>Packing Rectangles =
<BR><BR>=C6=CC=B7=C5=BE=D8=D0=CE=BF=E9<BR><BR>IOI 95<BR><BR>=D2=EB by =
leontea</PRE><PRE><IMG class=3Dblogimg =
src=3D"http://hiphotos.baidu.com/leokan/pic/item/b9c6c78050a12bd89023d904=
.jpg" border=3D0 =
small=3D"0"></PRE><PRE><BR><BR><BR><BR><BR><BR>=B8=F8=B6=A84=B8=F6=BE=D8=D0=
=CE=BF=E9=A3=AC=D5=D2=B3=F6=D2=BB=B8=F6=D7=EE=D0=A1=B5=C4=B7=E2=B1=D5=BE=D8=
=D0=CE=BD=AB=D5=E24=B8=F6=BE=D8=D0=CE=BF=E9=B7=C5=C8=EB=A3=AC=B5=AB=B2=BB=
=B5=C3=CF=E0=BB=A5=D6=D8=B5=FE=A1=A3=CB=F9=CE=BD=D7=EE=D0=A1=BE=D8=D0=CE=D6=
=B8=B8=C3=BE=D8=D0=CE=C3=E6=BB=FD=D7=EE=D0=A1=A1=A3<BR>=CB=F9=D3=D04=B8=F6=
=BE=D8=D0=CE=BF=E9=B5=C4=B1=DF=B6=BC=D3=EB=B7=E2=B1=D5=BE=D8=D0=CE=B5=C4=B1=
=DF=CF=E0=C6=BD=D0=D0=A3=AC=CD=BC1=CA=BE=B3=F6=C1=CB=C6=CC=B7=C54=B8=F6=BE=
=D8=D0=CE=BF=E9=B5=C46=D6=D6=B7=BD=B0=B8=A1=A3=D5=E26=D6=D6=B7=BD=B0=B8=BD=
=F6=D6=BB=CA=C7=BF=C9=C4=DC=B5=C4=BB=F9=B1=BE=C6=CC=B7=C5=B7=BD=B0=B8=A1=A3=
=D2=F2=CE=AA=C6=E4=CB=FC=B7=BD=B0=B8=C4=DC=D3=C9=BB=F9=B1=BE=B7=BD=B0=B8=CD=
=A8=B9=FD=D0=FD=D7=AA=BA=CD=BE=B5=CF=F1=B7=B4=C9=E4=B5=C3=B5=BD=A1=A3<BR>=
=BF=C9=C4=DC=B4=E6=D4=DA=C2=FA=D7=E3=CC=F5=BC=FE=C7=D2=D3=D0=D7=C5=CD=AC=D1=
=F9=C3=E6=BB=FD=B5=C4=B8=F7=D6=D6=B2=BB=CD=AC=B5=C4=B7=E2=B1=D5=BE=D8=D0=CE=
=A3=AC=C4=E3=D3=A6=B8=C3=CA=E4=B3=F6=CB=F9=D3=D0=D5=E2=D0=A9=B7=E2=B1=D5=BE=
=D8=D0=CE=B5=C4=B1=DF=B3=A4=A1=A3<BR><BR><BR>PROGRAM NAME: =
packrec<BR>INPUT =
FORMAT<BR>=B9=B2=D3=D04=D0=D0=A1=A3=C3=BF=D2=BB=D0=D0=D3=C3=C1=BD=B8=F6=D5=
=FD=D5=FB=CA=FD=C0=B4=B1=ED=CA=BE=D2=BB=B8=F6=B8=F8=B6=A8=B5=C4=BE=D8=D0=CE=
=BF=E9=B5=C4=C1=BD=B8=F6=B1=DF=B3=A4=A1=A3=BE=D8=D0=CE=BF=E9=B5=C4=C3=BF=CC=
=F5=B1=DF=B5=C4=B1=DF=B3=A4=B7=B6=CE=A7=D7=EE=D0=A1=CA=C71=A3=AC=D7=EE=B4=
=F3=CA=C750=A1=A3<BR><BR><BR>SAMPLE INPUT (file packrec.in)<BR>1 2<BR>2 =
3<BR>3 4<BR>4 5<BR><BR>OUTPUT =
FORMAT<BR>=D7=DC=D0=D0=CA=FD=CE=AA=BD=E2=B5=C4=D7=DC=CA=FD=BC=D31=A1=A3=B5=
=DA=D2=BB=D0=D0=CA=C7=D2=BB=B8=F6=D5=FB=CA=FD=A3=AC=B4=FA=B1=ED=B7=E2=B1=D5=
=BE=D8=D0=CE=B5=C4=D7=EE=D0=A1=C3=E6=BB=FD=A3=A8=D7=D3=C8=CE=CE=F1A=A3=A9=
=A1=A3=BD=D3=CF=C2=C0=B4=B5=C4=C3=BF=D2=BB=D0=D0=B6=BC=B1=ED=CA=BE=D2=BB=B8=
=F6=BD=E2=A3=AC=D3=C9=CA=FDP=BA=CD=CA=FDQ=C0=B4=B1=ED=CA=BE=A3=AC=B2=A2=C7=
=D2P=A1=DCQ=A3=A8=D7=D3=C8=CE=CE=F1B=A3=A9=A1=A3=D5=E2=D0=A9=D0=D0=B1=D8=D0=
=EB=B8=F9=BE=DDP=B5=C4=B4=F3=D0=A1=B0=B4=C9=FD=D0=F2=C5=C5=C1=D0=A3=ACP=D0=
=A1=B5=C4=D0=D0=D4=DA=C7=B0=A3=AC=B4=F3=B5=C4=D4=DA=BA=F3=A1=A3=C7=D2=CB=F9=
=D3=D0=D0=D0=B6=BC=D3=A6=CA=C7=B2=BB=CD=AC=B5=C4=A1=A3<BR><BR>SAMPLE =
OUTPUT (file packrec.out)<BR>40<BR>4 10<BR>5 8</PRE><PRE><HR><STRONG> =
=D5=E2=CC=E2=A3=AC=CA=B5=D4=DA=CC=AB=C2=E9=B7=B3=C1=CB=A3=AC=B6=D4=D3=DA=C7=
=B03=D6=D6=C7=E9=D3=C3=CC=B0=D0=C4+=C3=B6=BE=D9=A3=AC=B5=DA=D2=BB=D6=D6=A3=
=AC=C8=AB=B2=BF=CA=FA=D7=C5=B0=DA=A3=AC=B5=DA=B6=FE=D6=D63=CA=FA=D7=C5=A3=
=AC=C1=ED=CD=E2=D2=BB=B8=F6=BA=E1=D7=C5=A3=AC=B5=DA=C8=FD=D6=D63=B8=F6=CA=
=FA=D7=C5=C8=BB=BA=F3=C1=ED=CD=E2=D2=BB=B8=F6=D4=DA=CF=C2=C3=E6=B5=C4=BA=E1=
=D7=C5=BB=F2=D5=DF=CA=FA=D7=C5=A3=AC=B5=DA=CB=C4=B5=DA=CE=E5=D6=D6=BE=CD=C3=
=B6=BE=D9=D2=BB=CF=C2=CB=FC=B5=C4=CE=BB=D6=C3=BA=C3=C1=CB=A3=AC=B5=DA6=D6=
=D6=BB=B9=CA=C7=C3=B6=BE=D9=A1=A3=D5=E2=B4=CE=B5=C4=B4=FA=C2=EB=D0=B4=B5=C4=
=CC=AB=B3=F3=C1=CB=A3=AC=D3=D6=B3=A4=D3=D6=B3=F4=A3=AC=CE=D2=B5=F7=CA=D4=BB=
=B9=BA=C3=BE=C3=B2=C5=CD=A8=B9=FD=C4=D8=A3=AC=B2=BB=CC=FB=B3=F6=C0=B4=C1=CB=
=A1=A3</STRONG></PRE><PRE><STRONG><HR></STRONG></PRE>
=
<P><STRONG>usaco=B5=C4=B7=D6=CE=F6=A3=AC=D2=B2=CA=C7=B2=EE=B2=BB=B6=E0=B5=
=C4=B0=EC=B7=A8=A1=A3</STRONG></P>
<CENTER><STRONG><FONT size=3D7>Packing Rectangles</FONT><BR>Russ =
Cox=20
</STRONG></CENTER>
<P><STRONG>This program is straightforward, but a bit long due to =
the=20
geometry involved. </STRONG></P>
<P><STRONG>There are 24 permutations of the 4 rectangles, and for =
each=20
permutation, 16 different ways to orient them. We generate all =
such=20
orientations of permutations, and put the blocks together in each =
of the 6=20
different ways, recording the smallest rectangles we find. =
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef struct Rect Rect;
struct Rect {
int wid;
int ht;
};
Rect
rotate(Rect r)
{
Rect nr;
nr.wid =3D r.ht;
nr.ht =3D r.wid;
return nr;
}
int
max(int a, int b)
{
return a > b ? a : b;
}
int
min(int a, int b)
{
return a < b ? a : b;
}
int tot;
int bestarea;
int bestht[101];
void
record(Rect r)
{
int i;
if(r.wid*r.ht < tot)
*(long*)0=3D0;
if(r.wid*r.ht < bestarea || bestarea =3D=3D 0) {
bestarea =3D r.wid*r.ht;
for(i=3D0; i<=3D100; i++)
bestht[i] =3D 0;
}
if(r.wid*r.ht =3D=3D bestarea)
bestht[min(r.wid, r.ht)] =3D 1;
}
void
check(Rect *r)
{
Rect big;
int i;
/* schema 1: all lined up next to each other */
big.wid =3D 0;
big.ht =3D 0;
for(i=3D0; i<4; i++) {
big.wid +=3D r[i].wid;
big.ht =3D max(big.ht, r[i].ht);
}
record(big);
/* schema 2: first three lined up, fourth on bottom */
big.wid =3D 0;
big.ht =3D 0;
for(i=3D0; i<3; i++) {
big.wid +=3D r[i].wid;
big.ht =3D max(big.ht, r[i].ht);
}
big.ht +=3D r[3].ht;
big.wid =3D max(big.wid, r[3].wid);
record(big);
/* schema 3: first two lined up, third under them, fourth to side */
big.wid =3D r[0].wid + r[1].wid;
big.ht =3D max(r[0].ht, r[1].ht);
big.ht +=3D r[2].ht;
big.wid =3D max(big.wid, r[2].wid);
big.wid +=3D r[3].wid;
big.ht =3D max(big.ht, r[3].ht);
record(big);
/* schema 4, 5: first two rectangles lined up, next two stacked */
big.wid =3D r[0].wid + r[1].wid;
big.ht =3D max(r[0].ht, r[1].ht);
big.wid +=3D max(r[2].wid, r[3].wid);
big.ht =3D max(big.ht, r[2].ht+r[3].ht);
record(big);
/*
* schema 6: first two pressed next to each other, next two on top, =
like:=20
* 2 3
* 0 1
*/
big.ht =3D max(r[0].ht+r[2].ht, r[1].ht+r[3].ht);
big.wid =3D r[0].wid + r[1].wid;
/* do 2 and 1 touch? */
if(r[0].ht < r[1].ht)
big.wid =3D max(big.wid, r[2].wid+r[1].wid);
/* do 2 and 3 touch? */
if(r[0].ht+r[2].ht > r[1].ht)
big.wid =3D max(big.wid, r[2].wid+r[3].wid);
/* do 0 and 3 touch? */
if(r[1].ht < r[0].ht)
big.wid =3D max(big.wid, r[0].wid+r[3].wid);
/* maybe 2 or 3 sits by itself */
big.wid =3D max(big.wid, r[2].wid);
big.wid =3D max(big.wid, r[3].wid);
record(big); =20
}
void
checkrotate(Rect *r, int n)
{
if(n =3D=3D 4) {
check(r);
return;
}
checkrotate(r, n+1);
r[n] =3D rotate(r[n]);
checkrotate(r, n+1);
r[n] =3D rotate(r[n]);
}
void
checkpermute(Rect *r, int n)
{
Rect t;
int i;
if(n =3D=3D 4)
checkrotate(r, 0);
for(i=3Dn; i<4; i++) {
t =3D r[n], r[n] =3D r[i], r[i] =3D t; /* swap r[i], r[n] */
checkpermute(r, n+1);
t =3D r[n], r[n] =3D r[i], r[i] =3D t; /* swap r[i], r[n] */
}
}
void
main(void)
{
FILE *fin, *fout;
Rect r[4];
int i;
fin =3D fopen("packrec.in", "r");
fout =3D fopen("packrec.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
for(i=3D0; i<4; i++)
fscanf(fin, "%d %d", &r[i].wid, &r[i].ht);
=
tot=3D(r[0].wid*r[0].ht+r[1].wid*r[1].ht+r[2].wid*r[2].ht+r[3].wid*r[3].h=
t);
checkpermute(r, 0);
fprintf(fout, "%d\n", bestarea);
for(i=3D0; i<=3D100; i++)
if(bestht[i])
fprintf(fout, "%d %d\n", i, bestarea/i);
exit(0);
}</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
href=3D"http://hi.baidu.com/leokan/modify/blog/c5076181c65140dcbd3e1e73">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/c5076181c65140dcbd3e1e73.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3Dc5076181c65140dcbd3e1e73=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback(para)
{
var o_pop=3Dpara["popup"];
o_pop.config.contentType=3D1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=3Do_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
//-->
</SCRIPT>
| <A =
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/c5076181c65140dcbd3e1e73.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D =
[true,'=D7=F6=D2=BB=BC=FE=CE=DE=C1=C4=CA=C2=A3=ACusaco=B5=C4pas=D4=B4=CE=C4=
=BC=FE=B4=B4=BD=A8=CD=B5=C0=C1=B3=CC=D0=F2', =
'=D7=F6=D2=BB=BC=FE=CE=DE=C1=C4=CA=C2=A3=ACusaco=B5=C4pas=D4=B4=CE=C4=BC=FE=
...','/leokan/blog/item/e0e8382a3aea483c5243c117.html'];
var post =3D [true,'USACO 1.5.1 Number Triangles =CC=E2=BD=E2','USACO =
1.5.1 Number Triangles ...', =
'/leokan/blog/item/060b0224c1d08037c9955957.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -