Tagy: zametanie
Obtiažnosť: easy

Obdĺžniky 0

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:

  • Obdĺžnikov je nanajvýš $250$.
  • Všetky súradnice ich vrcholov ležia v uzavretom intervale $[0, 500]$.

Vyrieš túto úlohu čo najpohodlnejším spôsobom. (Hint: Dvojrozmerné pole je tvoj kamarát.)

Vstup

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 500$ a $0 \leq y_1 < y_2 \leq 500$.

Výstup

Jeden riadok obsahujúci jedno číslo - obsah zjednotenia obdĺžnikov.

Príklady

Vstup

2
7 7 9 9
10 8 13 10

Výstup

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$.

Vstup

2
7 7 9 9
8 8 11 10

Výstup

9

Tie isté dva obdĺžniky, ale teraz sme jeden posunuli aby sa prekrývali. Obsah zjednotenia tým klesol.

Vstup

4
0 0 3 3
1 1 2 2
2 1 3 4
1 4 4 5

Výstup

13
    +---+---+---+
    |           |
    +---+---+---+
        |   |
+---+---+---+
|       |   |
+   +---+   +
|   |   |   |
+   +---+---+
|           |
+---+---+---+
Ak chceš riešiť túto úlohu, musíš sa najprv prihlásiť.