Državno natjecanje 2012. godine za 1. i 2. razred Srednje Škole - 1. zadatak

Državno natjecanje 2012. godine za 3. i 4. razred Srednje Škole - 1. zadatak

Bakljadom zbog sumljivog penala u Klingonskom derbiju cijeli travnjak nogometnog igrališta je uništen. Izvršni dopredsjednik (Darth Vader) nogometnog kluba domaćina, odlučio je žurno obnoviti travnjak. U tu je svrhu poslao robote koji posebnim metodama obnavljaju travnjak. Roboti uvijek obnavljaju travnjak u djelovima pravokutnog oblika. Zbog slabe koordinacije, neki djelovi su se preklapali i obnavljani su više puta (što nije imalo dodatnog pozitivnog efekta). Zbog toga travnjak stadiona nije u potpunosti obnovljen za dolazeći trening. Darth Vader je pod pritiskom navijača odlučio održati trening na najvećem obnovljenom i neprekinutom dijelu travnjaka. Obnovljeni dio smatramo neprekinutim ako se djelovi od kojih se sastoji preklapaju ili dodiruju (makar se dodirivali samo vrhovima).

Ako je poznato područje koje je obnovio svaki od robota izračunajte površinu najvećeg obnovljenog dijela travnjaka bez prekida.

Preko travnjaka postavimo koordinatni sustav s koordinatom (0,0) na centru terena. Svaki robot je obnovio dio pravokutnog oblika opisanog koordinatama (X1, Y1) i (X2, Y2), pri čemu vrijedi X1 < X2 i Y1 < Y2. Stranice obnovljenog dijela paralelne s koordinatnim osima.

ULAZNI PODACI

U prvom retku se nalazi prirodni broj N (1≤N≤1000) koji predstavlja broj robota koji su obnavljali travnjak. U slijedećih N redova se nalaze po četiri cijela broja X1, Y1, X2, Y2 (-500000≤ X1, Y1, X2, Y2 ≤ 500000) koji predstavljaju koordinate dijela kojeg je obnovio i-ti robot.

IZLAZNI PODACI

Ispisati jedan broj, površinu najvećeg obnovljenog i neprekinutog dijela travnjaka.

PRIMJERI TEST PODATAKA

ulaz

3
0 3 3 4
1 2 2 5
5 2 7 4

izlaz

5

ulaz

5
9 4 12 8
2 5 3 8
1 1 9 2
8 -3 9 2
8 1 12 3

izlaz

19

ulaz

5
1 4 3 6
3 2 5 4
5 4 7 6
8 1 9 5
9 1 10 5

izlaz

12