ac1093.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1093;
const
  maxn=2004;
var
  x,y,l:array[0..maxn]of cardinal;
  n,i,ans:cardinal;
procedure qsort(s,t:cardinal);
  var
    p,i,j,tx,ty:cardinal;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tx:=x[p];ty:=y[p];x[p]:=x[s];y[p]:=y[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (y[j]>=ty) do dec(j);
      if i=j then break;x[i]:=x[j];y[i]:=y[j];inc(i);
      while (i<j) and (y[i]<=ty) do inc(i);
      if i=j then break;x[j]:=x[i];y[j]:=y[i];dec(j);
    until i=j;
    x[i]:=tx;y[i]:=ty;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
procedure put(x:cardinal);
  var
    s,t,m:cardinal;
  begin
    s:=1;t:=ans+1;
    repeat
      m:=(s+t) shr 1;
      if x<=l[m] then
        if x>l[m-1] then break else t:=m-1
      else
        s:=m+1;
    until false;
    l[m]:=x;
    if m>ans then ans:=m;
  end;
begin
  repeat
    read(n,i,i);
    for i:=1 to n do
      read(x[i],y[i]);
    qsort(1,n);
    ans:=0;
    for i:=1 to n do begin
      l[ans+1]:=maxlongint*2+1;
      put(x[i]);
    end;
    writeln(ans);
  until seekeof;
end.