AREA - Diện tích hình chữ nhật

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const fi='';
      fo='';
      maxn=10010;
type ar=array[1..maxn*2] of longint;
var n,nh,nv,re:longint;
    x,y,h,v,d,e,xx,yy:ar;
    a,s:array[1..maxn*10] of longint;

procedure rf;
var i:longint;
begin
     read(n);
     for i:=1 to n do
     begin
          read(x[i*2-1],y[i*2-1],x[i*2],y[i*2]);
          xx[i*2-1]:=x[i*2]; xx[i*2]:=x[i*2-1];
     end;
     for i:=1 to n*2 do
     begin
          h[i]:=y[i]; v[i]:=x[i];
          d[i]:=i; e[i]:=i;
     end;
end;

procedure sort(var h,d:ar;l,r:longint);
var i,j,x,y:longint;
begin
     i:=l; j:=r; x:=h[(i+j) shr 1];
     repeat
           while h[i]<x do inc(i);
           while h[j]>x do dec(j);
           if i<=j then
           begin
                y:=h[i]; h[i]:=h[j]; h[j]:=y;
                y:=d[i]; d[i]:=d[j]; d[j]:=y;
                inc(i); dec(j);
           end;
     until i>j;
     if i<r then sort(h,d,i,r);
     if l<j then sort(h,d,l,j);
end;

procedure roirac;
var i:longint;
begin
     sort(h,d,1,n*2);
     nh:=1; y[d[1]]:=1;
     for i:=2 to n*2 do
     begin
          if h[i]<>h[nh] then
          begin
               inc(nh);
               h[nh]:=h[i];
          end;
          y[d[i]]:=nh;
     end;
     for i:=1 to n do dec(y[2*i]);
     for i:=1 to n do
     begin
          yy[i*2-1]:=y[i*2];
          yy[i*2]:=y[i*2-1];
     end;
end;

procedure add(node,l,r,x,y,val:longint);
var mid:longint;
begin
     if (l=x) and (r=y) then
     begin
          a[node]:=a[node]+val;
          if a[node]=1 then s[node]:=h[r+1]-h[l];
          if a[node]=0 then
          begin
               if l<r then s[node]:=s[node shl 1]+s[node shl 1+1]
               else s[node]:=0;
          end;
     end
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then add(node shl 1,l,mid,x,min(y,mid),val);
          if y>mid then add(node shl 1+1,mid+1,r,max(x,mid+1),y,val);
          if a[node]=0 then s[node]:=s[node shl 1]+s[node shl 1+1];
     end;
end;

procedure pr;
var i,t:longint;
begin
     roirac;
     sort(v,e,1,n*2);
     for i:=1 to n*2 do
     begin
          if i>1 then re:=re+(v[i]-v[i-1])*s[1];
          t:=e[i];
          if xx[t]>x[t] then add(1,1,n*2-1,y[t],yy[t],1)
          else add(1,1,n*2-1,yy[t],y[t],-1);
     end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Download