Cod sursa(job #16049)

Utilizator adalLica Adela adal Data 11 februarie 2007 23:24:27
Problema Pachete Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.97 kb
program pachete;
type rec=record
  s,d,c:longint;
end;
var  a,b:array[0..50000] of rec;
     sel:array[0..50000] of boolean;
     i,x,y,j,n,nr,x1,y1,lung:longint;
     f,g:text;
procedure egal(i,j:longint);
begin
    a[i].s:=b[j].s;
    a[i].d:=b[j].d;
    a[i].c:=b[j].c;
end;

procedure interclas(st,m,dr:longint);
var i,j,k,t:longint;
begin
  for i:=st to dr do begin
    b[i].s:=a[i].s;
    b[i].d:=a[i].d;
    b[i].c:=a[i].c;
  end;
  i:=st; j:=m+1; k:=st;
  while (i<=m) and(j<=dr) do
    if (b[i].c< b[j].c) then begin egal(k,j); inc(k); inc(j); end
      else begin egal(k,i); inc(i); inc(k); end;

  for t:=i to m do begin egal(k,t); inc(k); end;
  for t:=j to dr do begin egal(k,t); inc(k); end;
end;
procedure mergesort(st,dr:longint);
var  m:longint;
begin
  if st<>dr then begin
    m:=(st+dr) div 2;
    mergesort(st,m);
    mergesort(m+1,dr);
    interclas(st,m,dr);
 end;
end;

function incape(x1,y1,j:longint):boolean;
var xmin,xmax,ymin,ymax:longint;
begin
  if x>x1 then xmax:=x else xmax:=x1;
  if y>y1 then ymax:=y else ymax:=y1;
  if x<x1 then xmin:=x else xmin:=x1;
  if y<y1 then ymin:=y else ymin:=y1;
  if (a[j].s>=xmin) and(a[j].s<=xmax) and(a[j].d>=ymin) and(a[j].d<=ymax) then incape:=true
                                                                         else incape:=false;
end;

begin
 assign(f,'pachete.in'); reset(f);
 assign(g,'pachete.out'); rewrite(g);
 readln(f,n);  readln(f,x,y);
 for i:=1 to n do begin
    readln(f,a[i].s,a[i].d);
    a[i].c:=abs(a[i].s-x)+abs(y-a[i].d);
 end;
 mergesort(1,n);
 for i:=1 to n  do
   if sel[i]=false then begin
     sel[i]:=true; x1:=a[i].s; y1:=a[i].d; j:=i+1; lung:=a[i].c;
     while j<=n do begin
       if (a[j].c<lung) and
          incape(x1,y1,j) then begin
          x1:=a[j].s;
          y1:=a[i].d;
          sel[j]:=true;
          lung:=a[i].c;
       end;
      inc(j);
    end;
    inc(nr);
  end;
 writeln(g,nr);
close(f); close(g);
end.