apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

robredz Robežu redzamība 1 sek.


 Uzdevums

Fermeris Dons aplūko žogu, kas ierobežo viņam piederošo N“N metrus lielo plakano kvadrātveida lauku (2 ≤ N ≤ 500000). Žoga viens stūris atrodas sākumpunktā (0, 0), tam pretējais stūris atrodas punktā (N, N), bet žoga malas ir paralēlas X un Y asīm.

Žoga stabi atrodas ne tikai visos četros žoga stūros, bet arī ik pa metram visa žoga garumā. Tādējādi, pavisam ir 4×N žoga stabi. Žoga stabi ir vertikāli un uzskatīsim, ka tie ir tik tievi, ka tiem nav rādiusa. Fermeris Dons vēlas noteikt, cik stabus viņš var redzēt, ja viņš atrodas noteiktā punktā žoga iekšpusē.

Dona laukā atrodas R (1 ≤ R ≤ 30000) milzīgas klintis, kuras aizsedz viņa skatu uz dažiem žoga stabiem, jo viņš nav tik garš, lai redzētu pāri klintīm. Katras klints pamats ir izliekts daudzstūris ar nenulles laukumu un virsotnēm punktos, kuru koordinātu vērtības ir veseli skaitļi. Klintis ir ideāli vertikālas. Klintis savā starpā nepārklājas, nepieskaras viena otrai, nepieskaras Donam un žogam. Dons nepieskaras žogam, neatrodas nevienas klints iekšpusē vai uz tās.

Uzrakstiet programmu, kas dotam Dona žoga izmēram, klinšu novietojumam žoga iekšpusē un Dona atrašanās punktam, nosaka, cik žoga stabus Dons no šī punkta var redzēt. Gadījumā, ja klints pamata virsotne, žoga staba pamats un Dona atrašanās punkts atrodas uz vienas taisnes, Dons šo stabu neredz.

 
 Ievaddati

Ievaddatu faila robredz.dat pirmajā rindā doti divi naturāli skaitļi N un R, kas atdalīti ar tukšumsimbolu.

Ievaddatu faila otrajā rindā doti divi naturāli skaitļi X un Y, kas atdalīti ar tukšumsimbolu un apzīmē fermera Dona atrašanās koordinātas žoga iekšpusē.

Ievaddatu faila atlikušajā daļā ir aprakstītas R klintis: o i-tās klints apraksts sākas ar rindu, kas satur vienu naturālu skaitli pi (3 ≤ pi ≤ 20) - klints pamatu aprakstošo punktu skaitu. o Katrā no nākošajām pi faila rindām doti divi naturāli skaitļi, kas atdalīti ar tukšumsimbolu - kāda pamata punkta X un Y koordinātas. Klints pamata punkti ir atšķirīgi un uzdoti secībā, kas pretēja pulksteņrādītāja kustības virzienam. Savienojot šos punktus pēc kārtas ar nogriežņiem, iegūst izliektu daudzstūri.

 
 Izvaddati

Izvaddatu faila robredz.rez vienīgajā rindā jāizvada viens vesels skaitlis - žoga stabu skaits, kurus Dons no sava atrašanās punkta var redzēt.

 
 Piemērs

robredz.datrobredz.rez
100 1
60 50
5
70 40
75 40
80 40
80 50
70 60
319

Ievērojiet, ka klints pamatam ir trīs punkti, kas atrodas uz vienas taisnes: (70,40), (75,40) un (80,40).

 
 Atsauces
Uzdevums izmantots Vispasaules 15.informātikas olimpiādē IOI'2003 Kenošā(ASV) 2003.gadā.

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS