Zadanie: Prawoskrętny wielbłąd
Bajtocja składa się z N oaz leżących na pustyni, przy czym żadne
trzy oazy nie leżą na jednej linii prostej.
Bajtazar mieszka w jednej z nich, a w każdej z pozostałych ma po
jednym znajomym.
Bajtazar chce odwiedzić jak najwięcej swoich znajomych.
Zamierza pojechać na swoim wielbłądzie.
Wielbłąd ten porusza się niestety w dosyć ograniczony sposób:
- Po wyjściu z oazy wielbłąd porusza się po linii prostej,
aż dotrze do innej oazy.
- Wielbłąd skręca tylko w oazach, jednak tylko w prawo, o kąt
z przedziału
[0o;180o]
(wielbłąd może tylko raz obrócić się w oazie, tzn. nie jest
dozwolony n.p. obrót o 200o w wyniku dwóch kolejnych
obrotów o 100o)
- Wielbłąd nie chce chodzić po własnych śladach.
Pomóż Bajtazarowi tak ustalić trasę podróży, aby odwiedził jak
najwięcej znajomych.
Powinna ona zaczynać i kończyć się w oazie, w której mieszka Bajtazar.
Musi składać się z odcinków łączących kolejno odwiedzane oazy.
Trasa ta nie może dwa razy przechodzić przez ten sam punkt, z wyjątkiem
oazy Bajtazara, gdzie wielbłąd pojawia się dwukrotnie:
na początku i na końcu trasy.
Początkowo wielbłąd Bajtazara jest już ustawiony w kierunku konkretnej
oazy i musi wyruszyć w tym kierunku.
Ustawienie wielbłąda po powrocie z podróży nie ma znaczenia.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia współrzędne oaz oraz ustawienie
wielbłąda,
- obliczy maksymalną liczbę znajomych, których Bajtazar może
odwiedzić zgodnie z powyższymi regułami,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia zapisana jest jedna liczba całkowita
N (
3 <= N <= 1 000) -- liczba oaz w Bajtocji.
Oazy są ponumerowane od 1 do N.
Bajtazar mieszka w oazie nr 1, a jego wielbłąd stoi zwrócony w stronę
oazy nr 2.
W kolejnych N wierszach umieszczone są współrzędne oaz.
W i + 1-ym wierszu znajdują się dwie liczby całkowite xi, yi
-- pozioma i pionowa współrzędna i-tej oazy --
oddzielone pojedynczym odstępem.
Wszystkie współrzędne są z zakresu od -16 000 do 16 000.
Wyjście
W pierwszym i jedynym wierszu wyjścia Twój program powinien wypisać
jedną liczbę całkowitą -- największą liczbę znajomych,
których może odwiedzić Bajtazar.
Przykład
Dla danych wejściowych:6
1 1
-1 4
0 -1
4 1
0 3
1 4
poprawną odpowiedzią jest:4