ac1097.pas

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

program tju1097;
const
  maxn=15000;
var
  x,y,col:array[1..maxn]of longint;
  count:array[1..maxn]of word;
  n,r,i,cols,ans,f:word;
procedure qsortdot(s,t:word);
  var
    p,i,j,tx,ty:longint;
  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) or (y[j]=ty) and (x[j]>tx)) 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) or (y[i]=ty) and (y[i]<tx)) 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;
    qsortdot(s,i-1);
    qsortdot(i+1,t);
  end;
procedure qsortcol(s,t:word);
  var
    p,i,j,tc:longint;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tc:=col[p];col[p]:=col[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (col[j]>=tc) do dec(j);
      if i=j then break;col[i]:=col[j];inc(i);
      while (i<j) and (col[i]<=tc) do inc(i);
      if i=j then break;col[j]:=col[i];dec(j);
    until i=j;
    col[i]:=tc;
    qsortcol(s,i-1);
    qsortcol(i+1,t);
  end;
function search(x:longint):word;
  var
    l,r,m:word;
  begin
    l:=1;r:=cols;
    repeat
      m:=(l+r) shr 1;
      if col[m]=x then break else if col[m]<x then l:=m+1 else r:=m-1;
    until false;
    search:=m;
  end;
procedure modify(x,y,d:longint);
  var
    i:word;
  begin
    for i:=x to cols do begin
      if col[i]-col[x]>r then exit;
      inc(count[i],d);
      if count[i]>ans then ans:=count[i];
    end;
  end;
begin
  repeat
    read(n,r);
    for i:=1 to n do begin
      read(x[i],y[i]);
      col[i]:=x[i];
    end;
    qsortdot(1,n);qsortcol(1,n);
    cols:=1;
    for i:=2 to n do
      if col[i]>col[i-1] then begin
        inc(cols);col[cols]:=col[i];
      end;
    for i:=1 to n do
      x[i]:=search(x[i]);

    fillchar(count,sizeof(count),0);ans:=0;f:=1;
    for i:=1 to n do begin
      while y[i]-y[f]>r do begin modify(x[f],y[f],-1);inc(f);end;
      modify(x[i],y[i],1);
    end;
    writeln(ans);
  until seekeof;
end.