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:
Vyrieš túto úlohu čo najpohodlnejším spôsobom. (Hint: Dvojrozmerné pole je tvoj kamarát.)
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$.
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
+---+---+---+
| |
+---+---+---+
| |
+---+---+---+
| | |
+ +---+ +
| | | |
+ +---+---+
| |
+---+---+---+