Cod sursa(job #11628)

Utilizator gurneySachelarie Bogdan gurney Data 31 ianuarie 2007 23:33:19
Problema Pachete Scor 70
Compilator fpc Status done
Runda Arhiva de probleme Marime 6.62 kb
program pachete;
  const
    fin='pachete.in';
    fout='pachete.out';
    nmax=50000;
  var
    px,py:array[1..nmax] of longint;
    qx,qy:array[1..4,0..nmax] of longint;
    tot:longint;
    q1,q2,q3,q4:longint;
    suby:array[1..50000] of longint;
    st,dr,mid,max,min:longint;
    n,x0,y0,x,y,i,j,k,l,m:longint;

function part_up(cad,st,dr:longint):longint;
  var
    i,j:longint;
    x,y:longint;
  begin
    i:=st-1;j:=dr+1;
    x:=qx[cad,st];y:=qy[cad,st];
    while i<j do
      begin
        repeat
          dec(j);
        until (qx[cad,j]<x)or((qx[cad,j]=x)and(qy[cad,j]<=y));
        repeat
          inc(i);
        until (qx[cad,i]>x)or((qx[cad,i]=x)and(qy[cad,i]>=y));
        if i<j then
          begin
            qx[cad,i]:=qx[cad,i] xor qx[cad,j];
            qx[cad,j]:=qx[cad,i] xor qx[cad,j];
            qx[cad,i]:=qx[cad,i] xor qx[cad,j];
            qy[cad,i]:=qy[cad,i] xor qy[cad,j];
            qy[cad,j]:=qy[cad,i] xor qy[cad,j];
            qy[cad,i]:=qy[cad,i] xor qy[cad,j];
          end;
      end;
    part_up:=j;
  end;

function part_down(cad,st,dr:longint):longint;
  var
    i,j:longint;
    x,y:longint;
  begin
    i:=st-1;j:=dr+1;
    x:=qx[cad,st];y:=qy[cad,st];
    while i<j do
      begin
        repeat
          dec(j);
        until (qx[cad,j]<x)or((qx[cad,j]=x)and(qy[cad,j]>=y));
        repeat
          inc(i);
        until (qx[cad,i]>x)or((qx[cad,i]=x)and(qy[cad,i]<=y));
        if i<j then
          begin
            qx[cad,i]:=qx[cad,i] xor qx[cad,j];
            qx[cad,j]:=qx[cad,i] xor qx[cad,j];
            qx[cad,i]:=qx[cad,i] xor qx[cad,j];
            qy[cad,i]:=qy[cad,i] xor qy[cad,j];
            qy[cad,j]:=qy[cad,i] xor qy[cad,j];
            qy[cad,i]:=qy[cad,i] xor qy[cad,j];
          end;
      end;
    part_down:=j;
  end;

procedure qsort(cad,st,dr:longint;up:boolean);
  var
    p:longint;
  begin
    if up then
      begin
        if st<dr then
          begin
            p:=part_up(cad,st,dr);
            qsort(cad,st,p,up);
            qsort(cad,p+1,dr,up);
          end;
      end
    else
      begin
        if st<dr then
          begin
            p:=part_down(cad,st,dr);
            qsort(cad,st,p,up);
            qsort(cad,p+1,dr,up);
          end;
      end;
  end;

begin
  assign(input,fin);
    reset(input);
    readln(n);
    readln(x0,y0);
    for i:=1 to n do
      readln(px[i],py[i]);
  close(input);
  assign(output,fout);
    rewrite(output);
    for i:=1 to n do
      begin
        if (px[i]>=x0) and (py[i]>=y0) then
          begin
            inc(qx[1,0]);
            qx[1,qx[1,0]]:=px[i]-x0;
            qy[1,qx[1,0]]:=py[i]-y0;
          end
        else if (px[i]<x0)and(py[i]>=y0) then
          begin
            inc(qx[2,0]);
            qx[2,qx[2,0]]:=px[i]-x0;
            qy[2,qx[2,0]]:=py[i]-y0;
          end
        else if (px[i]<x0) and (py[i]<y0) then
          begin
            inc(qx[3,0]);
            qx[3,qx[3,0]]:=px[i]-x0;
            qy[3,qx[3,0]]:=py[i]-y0;
          end
        else
          begin
            inc(qx[4,0]);
            qx[4,qx[4,0]]:=px[i]-x0;
            qy[4,qx[4,0]]:=py[i]-y0;
          end;
      end;
    if qx[1,0]>0 then
      begin
        q1:=1;
        qsort(1,1,qx[1,0],true);
        suby[1]:=qy[1,1];
        for i:=2 to qx[1,0] do
          begin
            st:=1;dr:=q1;
            mid:=(st+dr)shr 1;
            min:=maxint;y:=qy[1,i];
            while st<=dr do
              begin
                if suby[mid]<=y then
                  begin
                    dr:=mid-1;
                    if mid<min then
                      min:=mid;
                  end
                else
                  st:=mid+1;
                mid:=(st+dr)shr 1;
              end;
            if min<>maxint then
              begin
                suby[min]:=y;
              end
            else
              begin
                inc(q1);
                suby[q1]:=y;
              end;
          end;
      end;
    if qx[2,0]>0 then
      begin
        q2:=1;
        qsort(2,1,qx[2,0],false);
        suby[1]:=qy[2,qx[2,0]];
        for i:=qx[2,0]-1 downto 1 do
          begin
            st:=1;dr:=q2;
            mid:=(st+dr)shr 1;
            min:=maxint;y:=qy[2,i];
            while st<=dr do
              begin
                if suby[mid]<=y then
                  begin
                    dr:=mid-1;
                    if mid<min then
                      min:=mid;
                  end
                else
                  st:=mid+1;
                mid:=(st+dr)shr 1;
              end;
            if min<>maxint then
              begin
                suby[min]:=y;
              end
            else
              begin
                inc(q2);
                suby[q2]:=y;
              end;
          end;
      end;
    if qx[3,0]>0 then
      begin
        q3:=1;
        qsort(3,1,qx[3,0],true);
        suby[1]:=qy[3,qx[3,0]];
        for i:=qx[3,0]-1 downto 1 do
          begin
            st:=1;dr:=q3;
            mid:=(st+dr)shr 1;
            min:=maxint;y:=qy[3,i];
            while st<=dr do
              begin
                if suby[mid]>=y then
                  begin
                    dr:=mid-1;
                    if mid<min then
                      min:=mid;
                  end
                else
                  st:=mid+1;
                mid:=(st+dr)shr 1;
              end;
            if min<>maxint then
              begin
                suby[min]:=y;
              end
            else
              begin
                inc(q3);
                suby[q3]:=y;
              end;
          end;
      end;
    if qx[4,0]>0 then
      begin
        q4:=1;
        qsort(4,1,qx[4,0],false);
        suby[1]:=qy[4,1];
        for i:=2 to qx[4,0] do
          begin
            st:=1;dr:=q4;
            mid:=(st+dr)shr 1;
            min:=maxint;y:=qy[4,i];
            while st<=dr do
              begin
                if suby[mid]>=y then
                  begin
                    dr:=mid-1;
                    if mid<min then
                      min:=mid;
                  end
                else
                  st:=mid+1;
                mid:=(st+dr)shr 1;
              end;
            if min<>maxint then
              begin
                suby[min]:=y;
              end
            else
              begin
                inc(q4);
                suby[q4]:=y;
              end;
          end;
      end;
    writeln(q1+q2+q3+q4);
  close(output);
end.