Cod sursa(job #25413)

Utilizator cimiCristina Stancu-Mara cimi Data 4 martie 2007 12:31:11
Problema Ograzi Scor 50
Compilator fpc Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.94 kb
const
  lin=50050;
var
  oi:array[1..2] of longint;
  og:array[1..lin,1..4] of longint;
  i,j,n,m,w,h,ox,oy,sol:longint;
  b:boolean;

procedure Sort(l, r: longint);
var
  i, j, x, y, t: longint;
begin
  i := l; j := r; x := og[(l+r) DIV 2,3]; y:=og[(l+r) DIV 2,4];
  repeat
    while (og[i,3] < x) or ( (og[i,3] = x) and (og[i,4] < y) ) do inc(i);
    while (x < og[j,3]) or ( (x = og[j,3]) and (y < og[j,4]) ) do dec(j);
    if i <= j then
    begin
      t := og[i,1]; og[i,1] := og[j,1]; og[j,1] := t;
      t := og[i,2]; og[i,2] := og[j,2]; og[j,2] := t;
      t := og[i,3]; og[i,3] := og[j,3]; og[j,3] := t;
      t := og[i,4]; og[i,4] := og[j,4]; og[j,4] := t;
      inc(i); dec(j);
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

procedure search(lo,hi:longint);
var t:longint;
begin
  if lo>hi then exit;
  t:=(lo+hi) shr 1;
  if (og[t,3]=ox) and (og[t,4]=oy) then
  begin
    if (og[t,1]<=oi[1]) and (oi[1]<=og[t,1]+w) and (og[t,2]<=oi[2]) and (oi[2]<=og[t,2]+h) then b:=true;
    exit;
  end;
  if (not b) and ((og[t,3]>ox) or ((og[t,3]=ox)and(og[t,4]>oy))) then search(lo,t-1);
  if (not b) and ((og[t,3]<ox) or ((og[t,3]=ox)and(og[t,4]<oy))) then search(t+1,hi);
end;

begin
  assign(input,'ograzi.in');
  reset(input);
  readln(n,m,w,h);
  for i:=1 to n do
  begin
    read(og[i,1],og[i,2]);
    og[i,3]:=og[i,1] div w;
    og[i,4]:=og[i,2] div h;
  end;
  sort(1,n); sol:=0;
  for i:=1 to m do
  begin
    read(oi[1],oi[2]);
    b:=false;
    ox:=oi[1] div w;
    oy:=oi[2] div h;
    search(1,n);
    if not b then
    begin
      dec(ox);
      search(1,n);
    end;
    if not b then
    begin
      dec(oy);
      search(1,n);
    end;
    if not b then
    begin
      inc(ox);
      search(1,n);
    end;
    if b then
      inc(sol);
  end;
  close(input);
  assign(output,'ograzi.out');
  rewrite(output);
  writeln(sol);
  close(output);
end.