Cod sursa(job #25284)

Utilizator ViansiTudor Virgil Viansi Data 4 martie 2007 11:48:31
Problema Ograzi Scor 20
Compilator fpc Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 3.99 kb
program ograzi;
type
     pograda=^ograda;
     ograda=record
                  x,y:longint;
                  next,prev:pograda;
                  end;

     poaie=^oaie;
     oaie=record
                x,y:longint;
                next,prev:poaie;
                end;

var ogl,ogh:pograda;
    oil,oih:poaie;
    og:pograda;
    oi:poaie;
    n,m,lx,ly:longint;

procedure citire;
var f:text;
    i:longint;
    nog:pograda;
    noi:poaie;
begin
     Assign(f,'ograzi.in');
     Reset(f);
     read(f,n,m,lx,ly);
     new(ogl);
     ogh:=ogl;
     ogl^.next:=nil;
     ogl^.prev:=nil;
     read(f,ogl^.x,ogl^.y);
     for i:=2 to n do
     begin
          new(nog);
          nog^.next:=ogl;
          nog^.prev:=nil;
          ogl^.prev:=nog;
          ogl:=nog;
          read(f,ogl^.x,ogl^.y);
     end;
     new(oil);
     oih:=oil;
     oil^.next:=nil;
     oil^.prev:=nil;
     read(f,oil^.x,oil^.y);
     for i:=2 to m do
     begin
          new(noi);
          noi^.next:=oil;
          noi^.prev:=nil;
          oil^.prev:=noi;
          oil:=noi;
          read(f,oil^.x,oil^.y);
     end;
     Close(f);
end;

procedure sortograzibyx(Lo,Hi:integer;ogl,ogh:pograda);
var i,j,m,x:longint;
    ogi,ogj,ogm:pograda;
begin
     i:=Lo; j:=Hi; m:=(Lo+Hi) div 2;
     ogi:=ogl;
     ogj:=ogh;
     ogm:=ogi;
     for x:=i+1 to m do ogm:=ogm^.next;
     while i<j do
     begin
          while ogi^.x<ogm^.x do
          begin
               inc(i);
               ogi:=ogi^.next;
          end;
          while ogj^.x>ogm^.x do
          begin
               dec(j);
               ogj:=ogj^.prev;
          end;
          if i<=j then
          begin
               x:=ogi^.x;
               ogi^.x:=ogj^.x;
               ogj^.x:=x;
               x:=ogi^.y;
               ogi^.y:=ogj^.y;
               ogj^.y:=x;
               ogi:=ogi^.next;
               ogj:=ogj^.prev;
               inc(i);
               dec(j);
          end;
     end;
     if i<Hi then sortograzibyx(i,Hi,ogi,ogh);
     if j>Lo then sortograzibyx(Lo,j,ogl,ogj);
end;

procedure sortoibyx(Lo,Hi:integer;oil,oih:poaie);
var i,j,m,x:longint;
    oii,oij,oim:poaie;
begin
     i:=Lo; j:=Hi; m:=(Lo+Hi) div 2;
     oii:=oil;
     oij:=oih;
     oim:=oii;
     for x:=i+1 to m do oim:=oim^.next;
     while i<j do
     begin
          while oii^.x<oim^.x do
          begin
               inc(i);
               oii:=oii^.next;
          end;
          while oij^.x>oim^.x do
          begin
               dec(j);
               oij:=oij^.prev;
          end;
          if i<=j then
          begin
               x:=oii^.x;
               oii^.x:=oij^.x;
               oij^.x:=x;
               x:=oii^.y;
               oii^.y:=oij^.y;
               oij^.y:=x;
               oii:=oii^.next;
               oij:=oij^.prev;
               inc(i);
               dec(j);
          end;
     end;
     if i<Hi then sortoibyx(i,Hi,oii,oih);
     if j>Lo then sortoibyx(Lo,j,oil,oij);
end;

var ax,bx,cx,dx:longint;
    oigasite:longint;
    f:text;
begin
     {randomize;
     Assign(f,'ograzi.in');
     Rewrite(f);
     writeln(f,10000,' ',20000,' ',100,' ',100);
     for ax:=1 to 0000 do writeln(f,random(10000),' ',random(10000));
     for bx:=1 to 20000 do writeln(f,random(10000),' ',random(10000));
     Close(f);
     }
     oigasite:=0;

     citire;
     sortograzibyx(1,n,ogl,ogh);
     sortoibyx(1,m,oil,oih);

     og:=ogl;
     while og<>nil do
     begin
          ax:=og^.x;
          bx:=ax+lx;
          cx:=og^.y;
          dx:=cx+ly;
          oi:=oil;
          while (oi<>nil) and (oi^.x<ax) do oi:=oi^.next;
          while (oi<>nil) and (oi^.x<=bx) do
          begin
               if (oi^.y>=cx) and (oi^.y<=dx) then inc(oigasite);
               oi:=oi^.next;
          end;
          og:=og^.next;
     end;
     Assign(f,'ograzi.out');
     Rewrite(F);
     writeln(f,oigasite);
     Close(f);
end.