Dextrogyrate Camel

Time limit1sMemory limit512 MB

Summary

Find the longest closed camel route that starts at oasis 1 heading to oasis 2, always turns right by at most 180 degrees at each oasis, never crosses itself, and visits the most distinct oases.

Level: Hard9 of 10
Topics: Geometry, Dynamic programming, Greedy, Sorting
Solved: No attempts yet

Problem

Byteotia has $N$ oasis in the desert, and no three of them lie on one straight line. Byteasar lives in one of the oasis and has a friend in every other one, and he wants to visit as many friends as possible while riding his camel. The camel is stubborn and moves in its own peculiar way:

After leaving an oasis it travels in a straight line until it reaches another oasis.
It changes direction only at an oasis, and there it always turns to the right (clockwise) by an angle in the interval $[0°, 180°]$ . It makes exactly one turn at each oasis (it can never, for instance, turn by $200°$ as the result of two consecutive $100°$ turns).
The route never touches or crosses itself, and the camel never travels along a segment it has already used. The only oasis the route may pass through twice is Byteasar's home, where the journey both begins and ends.

At the start the camel stands at Byteasar's home oasis already facing one particular oasis, and it must set off straight toward that oasis. The direction the camel faces once it has returned home is irrelevant.

Find a route that starts and ends at Byteasar's home and lets him visit as many friends as possible.

Input

The first line contains one integer $N$ ( $3 \le N \le 1000$ ) — the number of oasis, numbered from $1$ to $N$ . Byteasar lives in oasis $1$ , and his camel initially faces oasis $2$ . Each of the following $N$ lines describes one oasis: the $i$ -th of them contains two integers $x_i$ and $y_i$ ( $-16000 \le x_i, y_i \le 16000$ ), the coordinates of oasis $i$ , separated by a single space.

Output

Print a single integer — the maximum number of friends Byteasar can visit. This equals the number of distinct oasis on the route other than his home oasis.

Hint

Examples5

Example 1
Input
```
6
1 1
-1 4
0 -1
4 1
0 3
1 4
```
Expected output
```
4
```
Example 2
Input
```
3
11 5
1 7
9 6
```
Expected output
```
2
```
Example 3
Input
```
4
-4 3
-5 4
1 -11
10 -9
```
Expected output
```
3
```

Example 4

Input

5
9916 1296
4297 -9030
-7260 -6877
-8784 4779
1831 9831

Expected output

Example 5

Input

8
0 -3
8 -10
4 -6
5 -9
-5 2
-6 -8
10 -1
-6 -1

Expected output