Unire rettangoli
Problem
Ci sono N rettangoli sul piano con vertici in punti con coordinate intere e lati paralleli agli assi delle coordinate. È necessario trovare l'area della loro unione.
Input
La prima riga del file di input contiene il numero N (0≤N ≤1500). Le successive N righe contengono 4 numeri interi x1, y1, x2, y2 — prima le coordinate dell'angolo in basso a sinistra del rettangolo, poi in alto a destra (0≤x1≤x2≤109, 0≤y1≤y2≤109). Nota che i rettangoli possono degenerare in linee e persino in punti.
Uscita
Produci un singolo numero — risposta al problema.
| Input |
Uscita |
|
3
1 1 3 5
5 2 7 4
2 4 6 7
|
23 |
|
2
0 0 2 2
1 3 2 4
|
5 |