packrec.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:packrec
}

program packrec;
const
  bin:array[0..15]of string[4]=('0000','0001','0010','0011','0100','0101','0110','0111','1000','1001','1010','1011','1100','1101','1110','1111');
var
  fin,fout:text;
  rec:array[1..4,0..1]of byte;
  s:set of 1..100;
  size:integer;
  i:byte;
function min(a,b:byte):byte;
  begin
    if a<b then min:=a else min:=b;
  end;
function max2(a,b:byte):byte;
  begin
    if a>b then max2:=a else max2:=b;
  end;
function max3(a,b,c:byte):byte;
  begin
    max3:=max2(max2(a,b),c);
  end;
function max4(a,b,c,d:byte):byte;
  begin
    max4:=max2(max2(a,b),max2(c,d));
  end;
procedure update(area:integer;p:byte);
  begin
    if area>size then exit;
    if area<size then begin size:=area;s:=[];end;
    s:=s+[p];
  end;
procedure arrange(layout,r1,r2,r3,r4:byte);
  var
    i:byte;
    p,q,p0,q0,a1,a2,a3,a4,b1,b2,b3,b4:byte;
    overlap:boolean;
  begin
    for i:=0 to 15 do begin
      a1:=rec[r1,ord(bin[i][1])-48];b1:=rec[r1,49-ord(bin[i][1])];
      a2:=rec[r2,ord(bin[i][2])-48];b2:=rec[r2,49-ord(bin[i][2])];
      a3:=rec[r3,ord(bin[i][3])-48];b3:=rec[r3,49-ord(bin[i][3])];
      a4:=rec[r4,ord(bin[i][4])-48];b4:=rec[r4,49-ord(bin[i][4])];
      overlap:=false;
      case layout of
        1:begin p:=a1+a2+a3+a4;q:=max4(b1,b2,b3,b4);end;
        2:begin p:=max2(a1,a2+a3+a4);q:=b1+max3(b2,b3,b4);end;
        3:begin p:=a1+max2(a2,a3+a4);q:=max2(b1,b2+max2(b3,b4));end;
        4:begin p:=max2(a1,a2)+a3+a4;q:=max3(b1+b2,b3,b4);end;
        5:begin
            if (a1<a4) and (a3<a2) and (b1<b2) and (b3<b4) or (a1>a4) and (a3>a2) and (b1>b2) and (b3>b4) then overlap:=true;
            if overlap then begin
              p:=max4(a1+a2,a3+a4,a1+a3,a2+a4);q:=max2(b1+b4,b2+b3);
              p0:=max2(a1+a2,a3+a4);q0:=max4(b1+b4,b2+b3,b1+b3,b2+b4);
            end
            else begin
              p:=max2(a1+a2,a3+a4);q:=max2(b1+b4,b2+b3);
            end;
          end;
      end;
      update(p*q,min(p,q));
      if overlap then update(p0*q0,min(p0,q0));
    end;
  end;
begin
  assign(fin,'packrec.in');
  reset(fin);
  for i:=1 to 4 do
    readln(fin,rec[i,0],rec[i,1]);
  close(fin);

  size:=10000;
  s:=[];

  arrange(1,1,2,3,4);

  arrange(2,1,2,3,4);
  arrange(2,2,1,3,4);
  arrange(2,3,1,2,4);
  arrange(2,4,1,2,3);

  arrange(3,1,2,3,4);
  arrange(3,1,3,2,4);
  arrange(3,1,4,2,3);
  arrange(3,2,1,3,4);
  arrange(3,2,3,1,4);
  arrange(3,2,4,1,3);
  arrange(3,3,1,2,4);
  arrange(3,3,2,1,4);
  arrange(3,3,4,1,2);
  arrange(3,4,1,2,3);
  arrange(3,4,2,1,3);
  arrange(3,4,3,1,2);

  arrange(4,1,2,3,4);
  arrange(4,1,3,2,4);
  arrange(4,1,4,2,3);
  arrange(4,2,3,1,4);
  arrange(4,2,4,1,3);
  arrange(4,3,4,1,2);

  arrange(5,1,3,2,4);
  arrange(5,1,2,3,4);
  arrange(5,1,2,4,3);

  assign(fout,'packrec.out');
  rewrite(fout);
  writeln(fout,size);
  for i:=1 to trunc(sqrt(size)) do
    if i in s then writeln(fout,i,' ',size div i);
  close(fout);
end.