Fusión de rectángulos
Problem
Hay N rectángulos en el plano con vértices en puntos con coordenadas enteras y lados paralelos a los ejes de coordenadas. Es necesario encontrar el área de su unión.
Entrada
La primera línea del archivo de entrada contiene el número N (0≤N ≤1500). Las siguientes N líneas contienen 4 enteros x1, y1, x2, y2 — primero las coordenadas de la esquina inferior izquierda del rectángulo, luego la esquina superior derecha (0≤x1≤x2≤109, 0≤y1≤y2≤109). Tenga en cuenta que los rectángulos pueden degenerar en líneas e incluso en puntos.
Salida
Producir un solo número — respuesta al problema.
Entrada |
Salida |
3
1 1 3 5
5 2 7 4
2 4 6 7
|
23 |
2
0 0 2 2
1 3 2 4
|
5 |