picture.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:picture
}

program picture;
const
  maxn=4999;
type
  edges=array[1..maxn*2]of integer;
  bools=array[1..maxn*2]of boolean;{True if it's a starting edge}
var
  fin,fout:text;
  x1,y1,x2,y2:array[1..maxn]of integer;
  n,i:integer;
  peri:longint;
procedure qsort(var a:edges;var b:bools;s,t:integer);
  var
    p,i,j,tint:integer;
    tbool:boolean;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tint:=a[p];tbool:=b[p];
    a[p]:=a[s];b[p]:=b[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (a[j]>=tint) do dec(j);
      if i=j then break;
      a[i]:=a[j];b[i]:=b[j];inc(i);
      while (i<j) and (a[i]<=tint) do inc(i);
      if i=j then break;
      a[j]:=a[i];b[j]:=b[i];dec(j);
    until i=j;
    a[i]:=tint;b[i]:=tbool;
    qsort(a,b,s,i-1);
    qsort(a,b,i+1,t);
  end;
procedure dostat;
  var
    h,w:edges;
    bh,bw:bools;
    i,j,height,ch,cw,c:integer;
  begin
    for i:=1 to n do begin
      h[i*2-1]:=y1[i];bh[i*2-1]:=true;
      h[i*2]:=y2[i];bh[i*2]:=false;
    end;
    qsort(h,bh,1,n*2);
    ch:=0;
    for i:=1 to n*2-1 do begin
      if bh[i] then inc(ch) else dec(ch);
      if (ch=0) or (h[i]=h[i+1]) then continue;
      height:=h[i+1]-h[i];
      c:=0;
      for j:=1 to n do
        if (y1[j]<=h[i]) and (y2[j]>=h[i+1]) then begin
          inc(c);
          w[c*2-1]:=x1[j];bw[c*2-1]:=true;
          w[c*2]:=x2[j];bw[c*2]:=false;
        end;
      qsort(w,bw,1,c*2);
      cw:=1;inc(peri,height);
      for j:=2 to c*2-1 do begin
        if bw[j] then inc(cw) else dec(cw);
        if (cw=0) and (w[j]<>w[j+1])
          or (cw=1) and bw[j] and (w[j]<>w[j-1])
            then inc(peri,height);
      end;
      inc(peri,height);
    end;
  end;
procedure flip;
  var
    i,t:integer;
  begin
    for i:=1 to n do begin
      t:=x1[i];x1[i]:=y1[i];y1[i]:=t;
      t:=x2[i];x2[i]:=y2[i];y2[i]:=t;
    end;
  end;
begin
  assign(fin,'picture.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do
    readln(fin,x1[i],y1[i],x2[i],y2[i]);
  close(fin);

  peri:=0;
  dostat;
  flip;
  dostat;

  assign(fout,'picture.out');
  rewrite(fout);
  writeln(fout,peri);
  close(fout);
end.