Cod sursa(job #14878)

Utilizator VmanDuta Vlad Vman Data 10 februarie 2007 01:05:35
Problema Pachete Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.44 kb
program pachete;
const nmax=50000;
type punct=record
                 x,y:longint;
           end;
     cadran=array[1..nmax]of word;
var c1,c2,c3,c4,l:cadran;
    p:array[1..nmax]of punct;
    x0,y0,xx,yy,i,nr,st,dr,m:longint;
    n,nr1,nr2,nr3,nr4,nrl:word;
    exista:boolean;
    f:text;


procedure citire;
begin
assign(f,'pachete.in');reset(f);
readln(f,n);
readln(f,x0,y0);
for i:=1 to n do begin
    readln(f,p[i].x,p[i].y);
    {cadranu 1}
    if (p[i].x<x0)and(p[i].y>y0) then
       begin
       inc(nr1);
       c1[nr1]:=i;
       end
    else
    {cadranu 2}
    if (p[i].x<x0)and(p[i].y<y0) then
       begin
       inc(nr2);
       c2[nr2]:=i;
       end
    else
    {cadranu 3}
    if (p[i].x>x0)and(p[i].y<y0) then
       begin
       inc(nr3);
       c3[nr3]:=i;
       end
    else
    {cadranu 4}
       begin
       inc(nr4);
       c4[nr4]:=i;
       end;
end;
close(f);
end;

procedure qsort(l, r: word;var c:cadran);
var
  i, j, m, y: longint;
begin
  i := l; j := r; m := p[c[(l+r) DIV 2]].x;
  repeat
    while p[c[i]].x < m do i := i + 1;
    while m < p[c[j]].x do j := j - 1;
    if i <= j then
    begin
      y := c[i]; c[i] := c[j]; c[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then qsort(l, j, c);
  if i < r then qsort(i, r, c);
end;


begin
citire;
nr:=0;
{cadranu 1}
if nr1<>0 then
begin
qsort(1,nr1,c1);
nrl:=1;
l[1]:=c1[1];
for i:=2 to nr1 do begin
        st:=1;
        dr:=nrl;
        while st+1<dr do begin
                m:=(st+dr) div 2;
                if p[l[m]].y>p[c1[i]].y then st:=m
                        else dr:=m;
        end;
        if p[l[dr]].y>p[c1[i]].y then l[dr]:=c1[i]
                else if p[l[st]].y>p[c1[i]].y then l[st]:=c1[i]
                        else begin inc(nrl);l[nrl]:=c1[i];end;
end;
inc(nr,nrl);
end;
{cadranu 2}
if nr2<>0 then
begin
qsort(1,nr2,c2);
nrl:=1;
l[1]:=c2[1];
for i:=2 to nr2 do begin
        st:=1;
        dr:=nrl;
        while st+1<dr do begin
                m:=(st+dr) div 2;
                if p[l[m]].y<p[c2[i]].y then st:=m
                        else dr:=m;
        end;
        if p[l[dr]].y<p[c2[i]].y then l[dr]:=c2[i]
                else if p[l[st]].y<p[c2[i]].y then l[st]:=c2[i]
                        else begin inc(nrl);l[nrl]:=c2[i];end;
end;
inc(nr,nrl);
end;
{cadranu 3}
if nr3<>0 then
begin
qsort(1,nr3,c3);
nrl:=1;
l[1]:=c3[1];
for i:=2 to nr3 do begin
        st:=1;
        dr:=nrl;
        while st+1<dr do begin
                m:=(st+dr) div 2;
                if p[l[m]].y>p[c3[i]].y then st:=m
                        else dr:=m;
        end;
        if p[l[dr]].y>p[c3[i]].y then l[dr]:=c3[i]
                else if p[l[st]].y>p[c3[i]].y then l[st]:=c3[i]
                        else begin inc(nrl);l[nrl]:=c3[i];end;
end;
inc(nr,nrl);
end;
{cadranu 4}
if nr4<>0 then
begin
qsort(1,nr4,c4);
nrl:=1;
l[1]:=c4[1];
for i:=2 to nr4 do begin
        st:=1;
        dr:=nrl;
        while st+1<dr do begin
                m:=(st+dr) div 2;
                if p[l[m]].y<p[c4[i]].y then st:=m
                        else dr:=m;
        end;
        if p[l[dr]].y<p[c4[i]].y then l[dr]:=c4[i]
                else if p[l[st]].y<p[c4[i]].y then l[st]:=c4[i]
                        else begin inc(nrl);l[nrl]:=c4[i];end;
end;
inc(nr,nrl);
end;
assign(f,'pachete.out');rewrite(f);
write(f,nr);
close(f);
end.