Polish version    English version  
  Historia OI -> XII OI 2004/2005 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

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





Wersja do druku