Mesclando Retângulos
Problem
Existem N retângulos no plano com vértices em pontos com coordenadas inteiras e lados paralelos aos eixos coordenados. É necessário encontrar a área de sua união.
Entrada
A primeira linha do arquivo de entrada contém o número N (0≤N ≤1500). As próximas N linhas contêm 4 inteiros x1, y1, x2, y2 — primeiro as coordenadas do canto inferior esquerdo do retângulo, depois o canto superior direito (0≤x1≤x2≤109, 0≤y1≤y2≤109). Observe que os retângulos podem degenerar em linhas e até mesmo em pontos.
Saída
Entre em um único número — resposta ao problema.
| Entrada |
Saída |
|
3
1 1 3 5
5 2 7 4
2 4 6 7
|
23 |
|
2
0 0 2 2
1 3 2 4
|
5 |