V rovine je nakreslených $n$ obdĺžnikov. Strany každého obdĺžnika sú rovnobežné so súradnicovými osami.
Vrcholy každého obdĺžnika majú celočíselné súradnice. Tvojou úlohou je vypočítať obsah ich zjednotenia.
V tejto verzii úlohy platia nasledovné obmedzenia:
Hú, nejak nám narástol rozsah súradníc. Pole rozmerov $10^9 \times 10^9$ sa nám do pamäte nezmestí, ani vyplniť ho v časovom limite nestíhame. Namiesto toho šikovne uprav svoj program riešiaci predchádzajúcu úlohu tak, aby vyriešil aj túto úlohu a pritom si vystačil s poľom rádovo takej istej veľkosti. (A daj pozor na to, aké veľké číslo môže byť teraz na výstupe.)
Na prvom riadku je $n$ - počet obdĺžnikov.
Nasleduje $n$ riadkov, každý popisujúci jeden obdĺžnik. Popis obdĺžnika má tvar
x1 y1 x2 y2, kde (x1, y1) a (x2, y2) sú celočíselné súradnice dvoch protiľahlých
vrcholov obdĺžnika. Platí, že $0 \leq x_1 < x_2 \leq 10^9$
a $0 \leq y_1 < y_2 \leq 10^9$.
Jeden riadok obsahujúci jedno číslo - obsah zjednotenia obdĺžnikov.
2
7 7 9 9
10 8 13 10
10
Prvý obdĺžnik má rozmery $2 \times 2$ a druhý $3 \times 2$. Keďže sa neprekrývajú, obsah ich zjednotenia je $4+6 = 10$.
2
7 7 9 9
8 8 11 10
9
Tie isté dva obdĺžniky, ale teraz sme jeden posunuli aby sa prekrývali. Obsah zjednotenia tým klesol.
4
0 0 3 3
1 1 2 2
2 1 3 4
1 4 4 5
13
+---+---+---+
| |
+---+---+---+
| |
+---+---+---+
| | |
+ +---+ +
| | | |
+ +---+---+
| |
+---+---+---+