Fusionner des rectangles
Problem
Il y a N rectangles sur le plan avec des sommets aux points avec des coordonnées entières et des côtés parallèles aux axes de coordonnées. Il faut trouver la zone de leur union.
Entrée
La première ligne du fichier d'entrée contient le nombre N (0≤N ≤1500). Les N lignes suivantes contiennent 4 entiers x1, y1, x2, y2 — d'abord les coordonnées du coin inférieur gauche du rectangle, puis le coin supérieur droit (0≤x1≤x2≤109, 0≤y1≤y2≤109). Notez que les rectangles peuvent dégénérer en lignes et même en points.
Sortie
Sortir un seul nombre — réponse au problème.
| Entrée |
Sortie |
3
1 1 3 5
5 2 7 4
2 4 6 7
23 |
2
0 0 2 2
1 3 2 4
5 |