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.

Download