AREA - Diện tích hình chữ nhật
Tác giả: ll931110
Ngôn ngữ: Pascal
Program AREA;
Const
input = '';
output = '';
Type
rec = record
low: longint;
high: longint;
open: boolean;
end;
arr = array[1..200000] of longint;
Var
x,number,cover,c: arr;
lab: array[1..200000] of rec;
n: longint;
S: int64;
Procedure init;
Var
f: text;
i: longint;
x1,y1,x2,y2: longint;
Begin
Assign(f, input);
Reset(f);
Readln(f, n);
For i:= 1 to n do
Begin
Read(f, x1, y1, x2, y2);
x[2 * i - 1]:= x1;
x[2 * i]:= x2;
with lab[2 * i - 1] do
Begin
low:= y1;
high:= y2;
open:= true;
End;
with lab[2 * i] do
Begin
low:= y1;
high:= y2;
open:= false;
End;
c[2 * i - 1]:= y1;
c[2 * i]:= y2;
End;
Close(f);
Fillchar(number, sizeof(number), 0);
Fillchar(cover, sizeof(cover), 0);
End;
Procedure quicksort1;
Procedure partition(l,h: longint);
Var
i,j,p,temp1: longint;
temp2: rec;
Begin
If l >= h then exit;
i:= l; j:= h; p:= x[random(h - l + 1) + l];
Repeat
While x[i] < p do inc(i);
While x[j] > p do dec(j);
If i <= j then
Begin
If i < j then
Begin
temp1:= x[i];
x[i]:= x[j];
x[j]:= temp1;
temp2:= lab[i];
lab[i]:= lab[j];
lab[j]:= temp2;
End;
inc(i);
dec(j);
End;
Until i > j;
partition(l,j);
partition(i,h);
End;
Begin
partition(1,2 * n);
End;
Procedure quicksort2;
Procedure partition(l,h: longint);
Var
i,j,p,temp1: longint;
Begin
If l >= h then exit;
i:= l; j:= h; p:= c[random(h - l + 1) + l];
Repeat
While c[i] < p do inc(i);
While c[j] > p do dec(j);
If i <= j then
Begin
If i < j then
Begin
temp1:= c[i];
c[i]:= c[j];
c[j]:= temp1;
End;
inc(i);
dec(j);
End;
Until i > j;
partition(l,j);
partition(i,h);
End;
Begin
partition(1,2 * n);
End;
Procedure open_true(A, B, k, l, h: longint);
Var
mid: longint;
Begin
If (h <= c[A]) or (c[B] <= l) then exit;
If (l <= c[A]) and (c[B] <= h) then
Begin
inc(number[k]);
cover[k]:= c[B] - c[A];
exit;
End;
If A + 1 >= B then exit;
mid:= (A + B) div 2;
open_true(A, mid, 2 * k, l, h);
open_true(mid, B, 2 * k + 1, l, h);
If number[k] = 0 then cover[k]:= cover[2 * k] + cover[2 * k + 1];
End;
Procedure open_false(A, B, k, l, h: longint);
Var
mid: longint;
Begin
If (h <= c[A]) or (c[B] <= l) then exit;
If (l <= c[A]) and (c[B] <= h) then
Begin
dec(number[k]);
If number[k] = 0 then
cover[k]:= cover[2 * k] + cover[2 * k + 1];
exit;
End;
If A + 1 >= B then
Begin
cover[k]:= 0;
exit;
End;
mid:= (A + B) div 2;
open_false(A, mid, 2 * k, l, h);
open_false(mid, B, 2 * k + 1, l, h);
If number[k] = 0 then cover[k]:= cover[2 * k] + cover[2 * k + 1];
End;
Procedure solve;
Var
f: text;
i: longint;
Begin
Assign(f, output);
Rewrite(f);
quicksort1;
quicksort2;
open_true(1, 2 * n, 1, lab[1].low, lab[1].high);
S:= 0;
For i:= 2 to 2 * n do
Begin
S:= S + cover[1] * (x[i] - x[i - 1]);
If lab[i].open then
open_true(1, 2 * n, 1, lab[i].low, lab[i].high)
else
open_false(1, 2 * n, 1, lab[i].low, lab[i].high);
End;
Writeln(f, S);
Close(f);
End;
Begin
init;
solve;
End.