Polish version    English version  
  History of OI

 About Olympic
 History of 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
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
 OI books
 National team
 Olympic camps
 Photo gallery

Task: Dextrogyrate camel

Byteotia consists of N oasis in the desert, no three of which are collinear. Byteasar lives in one of these oasis and moreover he has an acquaintance in every other. Byteasar wants to pay a visit to as many of them as possible. He plans to travel on the back of his camel. The camel is as obstinate as a mule and thus moves in its own peculiar way:

  • After departure from an oasis it moves along a straight line, until it gets to another oasis.
  • The camel turns only at oasis, but it turns only right (clockwise) and by an angle from the interval [0o;180o] (the camel makes only one turn at an oasis, i.e. it will not turn by e.g. 200o as a result of two subsequent turns by 100o)
  • The camel doesn't want to follow its own footprints.
Help Byteasar in planning such a route that he will be able to visit as many friends as possible. It should both begin and end in the oasis where Byteasar lives. It has to consist of segments connecting subsequently visited oasis. The route may not pass through any point two times, except the Byteasar's oasis, where the camel turns up twice: at the beginning and the end of the journey.

Byteasar's camel is initially facing a certain oasis and it has to start moving toward it. The direction the camel faces after returning from the journey is of no importance.


Write a programme that:
  • reads from the standard input the camel's coordinates and the direction it faces as well as the coordinates of the Byteotian oasis,
  • determines the maximum number of friends Byteasar can pay a visit to while sticking to the presented rules,
  • writes the result to the standard output.


In the first line of the standard input there is one integer N ( 3 <= N <= 1 000) -- the number of oasis in Byteotia. The oasis are numbered from 1 to N. Byteasar lives in the oasis no. 1 and his camel is facing the oasis no. 2. In the following N lines the coordinates of the oasis are given. In the (i + 1)th line there are two integers xi, yi -- the horizontal and vertical coordinate of the ith oasis -- separated by a single space. All coordinates are from the interval from -16 000 to 16 000.


In the first and only line of the standard output your programme should write one integer -- the maximum number of friends Byteasar can visit.


For the following input data:
1 1
-1 4
0 -1
4 1
0 3
1 4
the correct answer is:

Print friendly version