Posteri

Opis zadatka:

Nekoliko pravougaonih postera, fotografija i drugih slika su zalijepljeni na zid. Sve njihove strane su vertikalne ili horizontalne. Svaki pravougaonik može biti djelomicno ili potpuno pokriven nekim drugim pravougaonikom. Dužina granične linije unije svih pravougaonika se naziva obim. Potrebno je napisati program koji računa ovaj obim. Primjer sa sedam pravougaonika je prikazan na slici 1. Odgovarajuća granična linija je cijeli skup duži prikazan na slici 2.


Slika 1. Skup od 7 pravougaonika	Slika 2. Granicna linija skupa pravougaonika

Vrhovi svih pravougaonika imaju cjelobrojne koordinate. Izvršna verzija Vašeg programa se mora zvati POSTERI.EXE.

Ulazna datoteka:

Ulazni podaci moraju se nalaziti u tekstualnoj datoteci POSTERI.IN. Prva linija datoteke POSTERI.IN sadrži broj pravougaonika zalijepljenih na zid. U svakoj od slijedećih linija nalaze se cjelobrojne (integer) koordinate donjeg lijevog i gornjeg desnog vrha pravougaonika. Vrijednosti ovih koordinata su date kao uređeni parovi koji se sastoje od x-koordinate iza koje slijedi vrijednost y-koordinate.

Izlazna datoteka:

Izlazna datoteka POSTERI.OUT mora sadržavati samo jedan red sa nenegativnim cijelim brojem koji predstavlja traženi obim za date pravougaonike.

Vremensko ograničenje:

Za svaki testni primjer program treba da ponudi rješenje za najviše 30 sekundi.

Primjeri:

POSTERI.IN
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
POSTERI.OUT
228

Navedene datoteke odgovaraju primjeru sa slike 1.

Napomena:

Broj pravougaonika nije veći od 5000. Sve koordinate su iz intervala [-10000, 10000] i svaki dati pravougaonik ima pozitivnu površinu, to jest ne može se svesti na liniju ili tačku. Numerička vrijednost rezultata može zahtjevati 32-bitnu reprezentaciju (tip longint odnosno long).

[Testni podaci] [Rješenje (Pascal)] [Rješenje (C++)]