apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

daudzst Daudzstūris 1 sek.


 Uzdevums

Plaknē doti N punkti, kuru koordinātas ir naturāli skaitļi. Starp šiem punktiem nepieciešams atrast maksimāli daudz punktu, kas kopā ar koordinātu sākumpunktu var kalpot par izliekta daudzstūra virsotnēm. Daudzstūris ir izliekts, ja jebkurš nogrieznis, kura galapunkti atrodas daudzstūra virsotnēs, pilnībā pieder daudzstūrim. Divas secīgas daudzstūra malas nedrīkst būt paralēlas.

Uzrakstiet programmu, kas nosaka lielāko iespējamo šāda daudzstūra virsotņu skaitu!

 
 Ievaddati

Teksta faila daudzst.dat pirmajā rindā dota naturāla skaitļa N (punktu skaits, 2 ≤N≤100) vērtība.

Katrā no nākošajām N faila rindām dots pa diviem naturāliem skaitļiem X un Y (1 ≤X,Y≤100), kas atdalīti ar tukšumsimbolu. Katrs skaitļu pāris ir viena dotā punkta koordinātas. Visi punkti ir savā starpā atšķirīgi.

 
 Izvaddati

Teksta faila daudzst.rez vienīgajā rindā jāizvada naturāls skaitlis - lielākais iespējamais daudzstūra virsotņu skaits.

Piezīme: Rezultāts vienmēr būs vismaz 3.

 
 Piemērs

daudzst.datdaudzst.rez
5
4 2
2 2
2 3
3 2
3 1
4
  
daudzst.datdaudzst.rez
8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10
8
Piezīme: Šie punkti ir : (2;8),(3;9),(8;10),(9;10),(10;8),(10;3),(9;2),(0;0)
  
daudzst.datdaudzst.rez
10
9 6
1 7
2 2
3 9
8 7
3 2
9 4
3 1
9 7
6 9
7

 
 Atsauces
Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS