PBCPOINT - Nối điểm

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100001;
  MAXQ=10005;
var
  f1,f2:text;
  n,spt,first,last:longint;
  hang1,hang2,hang,cot1,cot2,cot:array[-1000..1000] of longint;
  inq:array[-1000..1000,1..2] of byte;
  qu,qt:array[1..MAXQ] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1);
  close(f2);
end;
procedure inp;
var
  i,x,y:longint;
begin
  for i:=-1000 to 1000 do
    begin
      hang1[i]:=1010; hang2[i]:=-1010;
      cot1[i]:=1010; cot2[i]:=-1010;
    end;
  read(f1,n);
  for i:=1 to n do
    begin
      read(f1,x,y);
      cot1[x]:=min(cot1[x],y);
      cot2[x]:=max(cot2[x],y);
      hang1[y]:=min(hang1[y],x);
      hang2[y]:=max(hang2[y],x);
    end;
  for i:=-1000 to 1000 do hang[i]:=max(hang2[i]-hang1[i]+1,0);
  for i:=-1000 to 1000 do cot[i]:=max(cot2[i]-cot1[i]+1,0);
end;
procedure ans;
var
  sum,i:longint;
begin
  sum:=0;
  for i:=-1000 to 1000 do
    sum+=hang[i];
  writeln(f2,sum);
end;
procedure solve;
var
  i,u,t:longint;
begin
  first:=1; last:=4002; spt:=4002;
  for i:=-1000 to 1000 do begin qu[i+1001]:=i; qt[i+1001]:=1; end;
  for i:=-1000 to 1000 do begin qu[i+3002]:=i; qt[i+3002]:=2; end;
  fillchar(inq,sizeof(inq),0);
  while spt>0 do
    begin
      u:=qu[first]; t:=qt[first]; inq[u,t]:=0;
      inc(first); if first=MAXQ then first:=1; dec(spt);
      if (hang[u]=0) and (t=1) then continue;
      if (cot[u]=0) and (t=2) then continue;
      if t=1 then
        begin
          for i:=hang1[u] to hang2[u] do
          if (u<cot1[i]) or (u>cot2[i]) then
            begin
              cot1[i]:=min(cot1[i],u);
              cot2[i]:=max(cot2[i],u);
              cot[i]:=cot2[i]-cot1[i]+1;
              if inq[i,2]=0 then
                begin
                  inc(last); if last=MAXQ then last:=1; inc(spt);
                  qu[last]:=i; qt[last]:=2; inq[i,2]:=1;
                end;
            end;
        end
      else // t=2
        begin
          for i:=cot1[u] to cot2[u] do
          if (u<hang1[i]) or (u>hang2[i]) then
            begin
              hang1[i]:=min(hang1[i],u);
              hang2[i]:=max(hang2[i],u);
              hang[i]:=hang2[i]-hang1[i]+1;
              if inq[i,1]=0 then
                begin
                  inc(last); if last=MAXQ then last:=1; inc(spt);
                  qu[last]:=i; qt[last]:=1; inq[i,1]:=1;
                end;
            end;
        end;
    end;
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Download