Section 1.4 Packing Rectangles

本来是USACO Training的1.4.1的,但是介于今早过了食物链想起了这道题实在是太怨念了,翻出自己写的AC程序居然有5KB!!

思路很简单,枚举,而且就图中的六种情况。但是第六种变化状况太多了,我自己根本就没写出来后来是看别人写的分四种情况Blah Blah...

可参考此篇中的分析:http://blog.sina.com.cn/s/blog_5c717d190100qgkr.html

Section 1.4 Packing Rectangles
program packrec;
var r,rw,rt:array[1..4,1..2] of integer;
    i,j,k,l,t,i1,j1,k1,l1:integer;
    ans,anscount:integer;
    ansx,ansy:array [0..200] of integer;

procedure swap(var a,b:integer);
var t:integer;
begin
  t:=a;a:=b;b:=t;
end;

procedure panding(x,y:integer);
begin
  if x*y<ans then
    begin
      ans:=x*y;
      anscount:=1;
      ansx[anscount]:=x;
      ansy[anscount]:=y;
      exit;
    end;
  if x*y=ans then
    begin
      inc(anscount);
      ansx[anscount]:=x;
      ansy[anscount]:=y;
    end;
end;

procedure work;
var lx,ly,min,i,max:integer;
begin
  {layout1}
  lx:=rw[1,1]+rw[2,1]+rw[3,1]+rw[4,1];
  ly:=0;
  for i:=1 to 4 do
    if rw[i,2]>ly then ly:=rw[i,2];
  panding(lx,ly);
  {layout2}
  lx:=rw[1,1]+rw[2,1]+rw[3,1];
  if rw[4,1]>lx then lx:=rw[4,1];
  max:=0;
  for i:=1 to 3 do
    if rw[i,2]>max then max:=rw[i,2];
  ly:=max+rw[4,2];
  panding(lx,ly);
  {layout3}
  lx:=rw[1,1]+rw[2,1];
  if rw[3,1]>lx then lx:=rw[3,1];
  lx:=lx+rw[4,1];
  ly:=rw[1,2]+rw[3,2];
  if rw[2,2]>rw[1,2] then ly:=rw[2,2]+rw[3,2];
  if rw[4,2]>ly then ly:=rw[4,2];
  panding(lx,ly);
  {layout4}
  if rw[2,1]>rw[3,1] then lx:=rw[2,1] else lx:=rw[3,1];
  lx:=lx+rw[1,1]+rw[4,1];
  ly:=rw[1,2];
  if rw[2,2]+rw[3,2]>ly then ly:=rw[2,2]+rw[3,2];
  if rw[4,2]>ly then ly:=rw[4,2];
  panding(lx,ly);
  {layout5}
  if rw[1,1]>rw[2,1] then lx:=rw[1,1] else lx:=rw[2,1];
  lx:=lx+rw[3,1]+rw[4,1];
  ly:=rw[1,2]+rw[2,2];
  if rw[3,2]>ly then ly:=rw[3,2];
  if rw[4,2]>ly then ly:=rw[4,2];
  panding(lx,ly);
  {layout6}
  {if (rw[1,1]+rw[3,1]>rw[2,1]+rw[4,1])  then
    lx:=rw[1,1]+rw[3,1]
  else
    lx:=rw[2,1]+rw[4,1];
  if rw[1,2]+rw[2,2]>rw[3,2]+rw[4,2] then
    ly:=rw[1,2]+rw[2,2]
  else
    ly:=rw[3,2]+rw[4,2];
  if (rw[3,2]>rw[1,2]) and (rw[1,1]<rw[2,1]) then ly:=rw[2,2]+rw[4,2];
  if (rw[1,1]>rw[2,1]) and (rw[3,2]>rw[2,2]) then ly:=rw[1,1]+rw[3,2];
  if (rw[1,1]>rw[2,1]) and (rw[3,2]>rw[)}
  if rw[1,2]+rw[2,2]>rw[3,2]+rw[4,2] then
    ly:=rw[1,2]+rw[2,2]
  else
    ly:=rw[3,2]+rw[4,2];
  if rw[2,2]>=rw[3,2]+rw[4,2] then
    begin
      lx:=rw[1,1];
      if rw[3,1]+rw[2,1]>lx then lx:=rw[3,1]+rw[2,1];
      if rw[4,1]+rw[2,1]>lx then lx:=rw[4,1]+rw[2,1];
    end;
  if (rw[2,2]>rw[4,2]) and (rw[2,2]>rw[3,2]+r[4,2]) then
    begin
      lx:=rw[1,1]+rw[3,1];
      if rw[2,1]+rw[3,1]>lx then lx:=rw[2,1]+rw[3,1];
      if rw[2,1]+rw[4,1]>lx then lx:=rw[2,1]+rw[4,1];
    end;
  if (rw[4,2]>rw[2,2]) and (rw[4,2]<rw[1,2]+rw[2,2]) then
    begin
      lx:=rw[1,1]+rw[3,1];
      if rw[1,1]+rw[4,1]>lx then lx:=rw[1,1]+rw[4,1];
      if rw[2,1]+rw[4,1]>lx then lx:=rw[2,1]+rw[4,1];
    end;
  if (rw[4,2]>=rw[1,2]+rw[2,2]) then
    begin
      lx:=rw[3,1];
      if rw[1,1]+rw[4,1]>lx then lx:=rw[1,1]+rw[4,1];
      if rw[2,1]+rw[4,1]>lx then lx:=rw[2,1]+rw[4,1];
    end;
  if rw[2,2]=rw[4,2] then
    begin
      lx:=rw[1,1]+rw[3,1];
      if rw[2,1]+rw[4,1]>lx then lx:=rw[2,1]+rw[4,1];
    end;
  panding(lx,ly);
end;


begin
  assign(input,packrec.in);reset(input);
  assign(output,packrec.out);rewrite(output);
  ans:=32766;
  for i:=1 to 4 do
    readln(r[i,1],r[i,2]);
  for i:=1 to 4 do
    for j:=1 to 4 do
      if (j<>i) then
        for k:=1 to 4 do
          if (k<>i) and (k<>j) then
            for l:=1 to 4 do
              if (l<>i) and (l<>j) and (l<>k) then
                begin
                  rw[1,1]:=r[i,1];rw[1,2]:=r[i,2];
                  rw[2,1]:=r[j,1];rw[2,2]:=r[j,2];
                  rw[3,1]:=r[k,1];rw[3,2]:=r[k,2];
                  rw[4,1]:=r[l,1];rw[4,2]:=r[l,2];
                  rt:=rw;
                  for i1:=0 to 1 do
                  for j1:=0 to 1 do
                  for k1:=0 to 1 do
                  for l1:=0 to 1 do
                    begin
                      rw:=rt;
                      if i1=1 then swap(rw[1,1],rw[1,2]);
                      if j1=1 then swap(rw[2,1],rw[2,2]);
                      if k1=1 then swap(rw[3,1],rw[3,2]);
                      if l1=1 then swap(rw[4,1],rw[4,2]);
                      work;
                    end;
                end;
  writeln(ans);
  for i:=1 to anscount-1 do
    for j:=i+1 to anscount do
      if ansx[i]<ansx[j] then
        begin
          swap(ansx[i],ansx[j]);
          swap(ansy[i],ansy[j]);
        end;
  for i:=1 to anscount do
    if (ansx[i]<>ansx[i-1]) and (ansx[i]>=ansy[i]) then writeln(ansy[i], ,ansx[i]);
  close(input);close(output);
end.
packrec

通过日期是2013-11-08,也就是因为NOIP和学农撞日期旷课在家的那个周五0 0,简直是无法忘记那天有多么郁闷,备考的一天简直废在这题上面…⊙﹏⊙b

Section 1.4 Packing Rectangles

上一篇:[itint5]判断是否为二叉搜索树


下一篇:hdu 2686 Matrix(DP)