Nosaukums
Daudzstūris (daudzst)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

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!


Ievaddatu raksturojums

Ievaddatu 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.


Izvaddatu raksturojums

Izvaddatu 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.


Piezīmes

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


Paraugdati

Stdin
5
4 2
2 2
2 3
3 2
3 1
Stdout
4

Stdin
8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10
Stdout
8

Stdin
10
9 6
1 7
2 2
3 9
8 7
3 2
9 4
3 1
9 7
6 9
Stdout
7

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.