car.pas

本光盘是《国际大学生程序设计竞赛例题解（一）》的配套光盘

Program Car;
var
 up,n1,m1,kills1,max,i,m,n,r,c:integer;
 x,y,a:array[1..100] of integer;



procedure solve(wx,wy:integer);
var free,aa,bb,k,r0:integer;
begin
 free:=n*m-wx*wy-c;
 r0:=r-free;
 if wx*wy<r0 then exit;

 if r0<=0 then begin
  k:=wx*wy;
  if k>max then
   max:=k;
  exit;
 end;

 for aa:=1 to wx do begin
  if aa=wx then bb:=0 else
   begin
    bb:=(r0-aa*wy) div (wx-aa);
    if r0<aa*wy then bb:=0 else
     if (r0-aa*wy) mod (wx-aa)<>0 then inc(bb);
   end;
  if (bb>=0) then begin
   k:=aa*wy+bb*wx-aa*bb;
   k:=wx*wy-k;
   if k>max then
    max:=k;
  end;
 end;

end;




procedure trys(i,wx,wy:integer);
var j:integer;
 begin

 if i>c then begin
  solve(wx,wy);
  exit
 end;

 for j:=1 to i-1 do begin
  if (x[j]=x[i]) and (a[j]=0) then begin
   a[i]:=0;
   trys(i+1,wx,wy);
   exit;
  end;
  if (y[j]=y[i]) and (a[j]=1) then begin
   a[i]:=1;
   trys(i+1,wx,wy);
   exit;
  end;
 end;

 a[i]:=0;
 trys(i+1,wx-1,wy);
 a[i]:=1;
 trys(i+1,wx,wy-1);
 a[i]:=0;

end;


begin
 assign(input,'car.in');reset(input);
 assign(output,'car.out');rewrite(output);
 readln(n,m,c,r);
 up:=n*m-c-r;
 max:=-1;
 for i:=1 to c do readln(x[i],y[i]);
 trys(1,n,m);
 writeln(max);
 close(output);
end.