Logu aizvēršana

ID: windows
Grūtība: 3/5
Laika limits: 1

Uzdevums

Kādā no populārām operāciju sistēmām ir iespējams atvērt daudz logus.

Katrs logs ir taisnstūris, kas sastāv no vienības kvadrātiņiem (katra kvadrātiņa izmērs ir 1*1).

Viss datora ekrāns sastāv no kvadrātiņiem, kas izvietoti 10000 rindās un 10000 kolonnās. Rindas tiek numurētas ar naturāliem skaitļiem no 1 pēc kārtas, sākot ar augšējo rindu uz leju, bet kolonnas - ar naturāliem skaitļiem no 1 pēc kārtas, sākot no kreisās puses uz labo. Tādējādi, ekrāna kreisā augšējā stūra kvadrātiņš atrodas pirmajā rindā un pirmajā kolonnā.

Jaunatvērtais logs, atkarībā no tā novietojuma, var (daļēji vai pilnībā) aizsegt vienu vai vairākus no iepriekš atvērtajiem logiem.

Jebkuru logu ir iespējams aizvērt ar datorpeles palīdzību, ja ir redzams šī loga labējā augšējā stūra kvadrātiņš. Tad, uzklikšķinot uz šī kvadrātiņa, logs tiks aizvērts. Kvadrātiņš nav redzams tikai tad, ja kāds vēlāk atvērts (un līdz šim neaizvērts) logs nosedz šo kvadrātiņu.

Uzrakstiet programmu, kas nosaka mazāko nepieciešamo peles klikšķu skaitu, kāds jāizdara, lai tiktu aizvērts logs, kurš tika atvērts pats pirmais!

 

Ievaddati

Teksta faila windows.in pirmajā rindā dota naturāla skaitļa N(atvērto logu skaits, 1 ≤N≤100) vērtība.

Katrā no nākošajām N rindām dots viena atvērtā loga apraksts kā četru naturālu skaitļu R1, K1, R2, K2 vērtības, ko atdala tukšumsimboli. Zināms, ka 1≤R1≤R2≤10000, 1≤K1≤K2 ≤10000. R1 un K1 apzīmē loga kreisā augšējā stūra kvadrātiņa rindas un kolonnas numuru, bet R2 un K2 apzīmē loga labā apakšējā stūra kvadrātiņa rindas un kolonnas numuru. Logi ir doti tieši tādā secībā, kādā tie tiek atvērti.

 

Izvaddati

Teksta faila windows.out vienīgajā rindā jāizvada naturāls skaitlis - mazākais nepieciešamais peles klikšķu skaits.

 

Piemērs

windows.inwindows.out
3
3 1 6 4
1 2 4 6
2 3 5 5
3
  
windows.inwindows.out
3
4 1 6 3
2 2 5 5
1 4 3 6
3
  
windows.inwindows.out
3
3 3 4 4
1 1 2 2
5 5 6 6
1

 

Atsauces

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā
© 2001-2002 olimps! http://www.lio.lv/olimps/