polygon |
Daudzstūri |
1 sek. |
Plaknē dota daudzstūru kopa, kurai izpildās sekojošas sakarības:
- nekādiem diviem daudzstūriem nav kopīgu punktu,
- katram daudzstūrim i ir Pi daudzstūri, kuru
iekšpusē tas atrodas un N-1-Pi daudzstūri, kas atrodas šī daudzstūra iekšpusē (0<=Pi<=N-1).
Uzrakstiet programmu, kas katram daudzstūrim nosaka to daudzstūru skaitu, kuru iekšpusē tas atrodas!
Teksta faila polygon.in pirmā rinda satur naturālu skaitli N - daudzstūru skaitu 3<=N<=10000.
Nākošajās N faila rindās ir dots pa vienam daudzstūra aprakstam katrā - i+1-ā faila rinda apraksta i-to daudzstūri.
Pirmais skaitlis katrā no šīm rindām Ci apraksta daudzstūra virsotņu skaitu , 3<=Ci<=20.
Nākošie Ci skaitļu pāri norāda kārtējās daudzstūra virsotnes koordinātas tā kontūra apiešanas secībā.
Virsotņu koordinātas uir veseli skaitļi diapazonā no -2000000000 līdz 2000000000.
Teksta faila polygon.out vienīgajā rindā jāizvada N veseli skaitļi - i- tajam skaitlim šajā rindā jābūt vienādam ar Pi - to daudzstūru, kuru iekšpusē atrodas i-tais daudzstūris, skaitam.
Starp katriem diviem blakus skaitļiem izvaddatos jābūt vienam tukšumsimbolam.
polygon.in | polygon.out |
3
3 -2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2
|
0 2 1
|
Uzdevums izmantots Ukrainas XV informātikas olimpiādē 2002.gadā.
Drukāšanai
|