Cod sursa(job #25343)

Utilizator girl_styleBianca Boeriu girl_style Data 4 martie 2007 12:07:39
Problema Ograzi Scor 30
Compilator fpc Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.95 kb
type sir=record
      x,y:longint;
     end;

     pct=record
      st,dr,vi,vf:longint;
     end;

var n,m,la,lu,nr:longint;
    d:array[1..50000] of sir;
    o:array[1..100000] of sir;
    h:array[1..122900] of pct;

procedure citire;
var i:longint;
begin
  assign(input,'ograzi.in');
  reset(input);
  readln(n,m,la,lu);
  for i:=1 to n do
    readln(d[i].x,d[i].y);
  for i:=1 to m do
    readln(o[i].x,o[i].y);
  close(input);
end;

procedure Sort(l, r: Integer);
var y:sir;
  i, j, x : integer;
begin
  i := l; j := r; x := o[(l+r) DIV 2].x;
  repeat
    while o[i].x < x do i := i + 1;
    while x < o[j].x do j := j - 1;
    if i <= j then
    begin
      y := o[i]; o[i] := o[j]; o[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

procedure constr(st,dr,vi,vf,nr:longint);
var mij:longint;
begin
  if st<dr then
    begin
      mij:=(st+dr) div 2;
      h[nr].st:=st;
      h[nr].dr:=dr;
      h[nr].vi:=vi;
      h[nr].vf:=vf;
      constr(st,mij,vi,o[mij].x,nr*2);
      constr(mij+1,dr,o[mij+1].x,vf,nr*2+1);
    end
           else
    begin
      h[nr].st:=st;
      h[nr].dr:=dr;
      h[nr].vi:=vi;
      h[nr].vf:=vf;
    end;
end;

procedure search(x1,x2,y1,y2,pas:longint);
begin
  if not((h[pas].vf<x1) or (h[pas].vi>x2)) then
    begin
      if h[pas].st=h[pas].dr then
        begin
          if (o[h[pas].st].y>=y1) and (o[h[pas].st].y<=y2) then
            nr:=nr+1;
        end
                             else
        begin
          search(x1,x2,y1,y2,pas*2);
          search(x1,x2,y1,y2,pas*2+1);
        end;
    end;
end;

procedure cauta;
var i:longint;
begin
  for i:=1 to n do
    search(d[i].x,d[i].x+la,d[i].y,d[i].y+lu,1);
  writeln(nr);
end;

begin
  assign(output,'ograzi.out');
  rewrite(output);
  citire;
  sort(1,m);
  constr(1,m,o[1].x,o[m].x,1);
  cauta;
  close(output);
end.