apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

vienktsn Vienkāršie taisnstūri 1 sek.


 Uzdevums

Kādu dienu garlaicības māktais Miķelītis uz rūtiņu lapas no viena līniju krustpunkta sāka zīmēt noslēgtu lauztu līniju, kas sastāvēja no horizontāliem un vertikāliem posmiem tā, ka:

  • katrs posms varēja krustot citus nogriežņus, bet nekad savā starpā nekrustojās divi vertikāli vai divi horizontāli nogriežņi;
  • katra posma beigu punkts vienlaikus ir nākošā posma sākumpunkts;
  • pēdējā posma beigu punkts sakrīt ar sākumpunktu.

Vienas šādas līnijas piemērs parādīts zīmējumā:

Posmi veido daudzstūrus, kuru malas veido taisnus leņķus. Miķelis cenšas noskaidrot, cik ir tādi vienkārši taisnstūri, kuru iekšpusē nav līnijas posmu. Dotajā piemērā ir trīs vienkārši taisnstūri: B, C un E. Ja apvienotu daudzstūrus C, D un E, tad arī iegūtu taisnstūri, bet tas nebūtu vienkāršs, jo tā iekšpusē ir līniju posmi.

Uzrakstiet programmu, kas nosaka vienkāršo taisnstūru skaitu Miķeļa zīmējumā!

 
 Ievaddati

Teksta faila vienktsn.dat pirmajā rindā dota naturāla skaitļa N (4≤N≤10000) vērtība - virsotņu skaits Miķeļa zīmējumā. Katrā no nākošajām N faila rindām doti divi nenegatīvi skaitļi x un y (0≤x,y≤10000) - vienas virsotnes x un y koordinātas. Starp skaitļiem ievaddatos ir viens tukšumsimbols.

 
 Izvaddati

Teksta faila vienktsn.rez vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - parasto taisnstūru skaits Miķelīša zīmējumā.

 
 Piemērs

vienktsn.datvienktsn.rez
16
1 7
2 7
2 4
6 4
6 8
8 8
8 2
3 2
3 5
9 5
9 3
11 3
11 1
5 1
5 3
1 3
3

 
 Atsauces
Uzdevums izmantots Korejas informātikas olimpiādē 2003.gadā

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS