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!
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.
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.
| daudzst.dat | daudzst.rez | |
5 4 2 2 2 2 3 3 2 3 1 |
4 |
|
| daudzst.dat | daudzst.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.dat | daudzst.rez | |
10 9 6 1 7 2 2 3 9 8 7 3 2 9 4 3 1 9 7 6 9 |
7 |