记录编号	149906	评测结果	AAAAA
题目名称	[IOI 1998] 矩形周长	最终得分	100
用户昵称	hjt	是否通过	通过
代码语言	Pascal	运行时间	0.018 s
提交时间	2015-02-27 00:16:51	内存使用	0.58 MiB

program zhouchang;
type node=record
       l,r,num,co,fl:longint;
       e,st:boolean;end;
var i,n,tot,t,rt,s,x1,y1,x2,nn,y2,nowy,ans:longint;
    tr:array[0..10000]of node;
    yline1,yline2,xline,y,ch:array[0..10000]of longint;

procedure swap(var a:longint;var b:longint);
var t:longint;
begin
  t:=a;
  a:=b;
  b:=t;
end;

procedure qsort(l,r:longint);
var j,k,mid:longint;
begin
  j:=l;
  k:=r;
  mid:=xline[(l+r) shr 1];
  repeat
    while xline[j]<mid do inc(j);
    while xline[k]>mid do dec(k);
    if j<=k then
      begin
        swap(xline[j],xline[k]);
        swap(yline1[j],yline1[k]);
        swap(yline2[j],yline2[k]);
        swap(ch[j],ch[k]);
        inc(j);
        dec(k);
      end;
  until j>k;
  if k>l then qsort(l,k);
  if j<r then qsort(j,r);
end;

procedure qsort2(l,r:longint);
var j,k,mid:longint;
begin
  j:=l;
  k:=r;
  mid:=y[(l+r) shr 1];
  repeat
    while y[j]<mid do inc(j);
    while y[k]>mid do dec(k);
    if j<=k then
      begin
        swap(y[j],y[k]);
        inc(j);
        dec(k);
      end;
  until j>k;
  if k>l then qsort2(l,k);
  if j<r then qsort2(j,r);
end;

procedure build(l,r,x:longint);
var mid:longint;
begin
  tr[x].l:=l;
  tr[x].r:=r;
  if l+1=r then exit;
  mid:=(l+r) shr 1;
  build(l,mid,2*x);
  build(mid,r,2*x+1);
end;

procedure pushup(x:longint);
begin
  if tr[x].fl>0 then
    begin
      tr[x].co:=y[tr[x].r]-y[tr[x].l];
      tr[x].num:=1;
      tr[x].st:=true;
      tr[x].e:=true;
    end
  else
    if tr[x].l+1=tr[x].r then
      begin
        tr[x].co:=0;
        tr[x].num:=0;
        tr[x].st:=false;
        tr[x].e:=false;
      end
    else
    begin
      tr[x].co:=tr[2*x].co+tr[2*x+1].co;
      tr[x].num:=tr[2*x].num+tr[2*x+1].num;
      if tr[2*x].e and tr[2*x+1].st then tr[x].num:=tr[x].num-1;
      tr[x].st:=tr[2*x].st;
      tr[x].e:=tr[2*x+1].e;
    end;
end;

procedure insert(l,r,x,v:longint);
var ll,rr,mid:longint;
begin
  ll:=y[tr[x].l];
  rr:=y[tr[x].r];
  if (l>rr) or (r<ll) then exit;
  if (l<=ll) and(r>=rr) then
    begin
      inc(tr[x].fl,v);
      pushup(x);
      exit;
    end;
  mid:=(tr[x].l+tr[x].r) shr 1;
  if not(tr[x].l+1=tr[x].r)and (l<y[mid])then insert(l,r,2*x,v);
  if not(tr[x].l+1=tr[x].r)and (r>y[mid])then insert(l,r,2*x+1,v);
  pushup(x);
end;

procedure init;
begin
  readln(n);
  for i:=1 to n do
    begin
      readln(x1,y1,x2,y2);
      inc(tot);
      yline1[tot]:=y1;
      yline2[tot]:=y2;
      y[tot]:=y1;
      xline[tot]:=x1;
      ch[tot]:=1;
      inc(tot);
      yline1[tot]:=y1;
      yline2[tot]:=y2;
      y[tot]:=y2;
      xline[tot]:=x2;
      ch[tot]:=-1;
    end;
end;

procedure pre;
begin
  s:=0;
  y[0]:=-1;
  for i:=1 to tot do
    if y[i]<>y[s] then begin inc(s);y[s]:=y[i];end;
  for i:=1 to tot do
    begin
      nn:=i;
      while (xline[nn]=xline[nn+1]) and (ch[nn]=-1) and (ch[nn+1]=1) do
        begin swap(ch[i],ch[i+1]);swap(yline1[i],yline1[i+1]);
              swap(yline2[i],yline2[i+1]);dec(nn);end;
    end;
end;

procedure main;
begin
  t:=1;
  nowy:=0;
  while t<tot  do
    begin
      insert(yline1[t],yline2[t],1,ch[t]);
      inc(ans,abs(tr[1].co-nowy));
      inc(ans,tr[1].num*2*(xline[t+1]-xline[t]));
      nowy:=tr[1].co;
      inc(t);
    end;
  insert(yline1[tot],yline2[tot],1,ch[tot]);
  inc(ans,abs(tr[1].co-nowy));
  writeln(ans);
end;

begin
  assign(input,'picture.in');reset(input);
  assign(output,'picture.out');rewrite(output);
  fillchar(tr,sizeof(tr),0);
  init;
  qsort(1,tot);
  qsort2(1,tot);
  pre;
  build(1,s,1);
  main;
  close(input);close(output);
end.