Boy Scout

Time limit1sMemory limit128 MB

Summary

Given N points in general position, find the longest closed route that always turns strictly left at every step, counting distinct points visited.

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

Problem

Every year the Boy Scouts hold their Olympics, and this year a new game is added.

The arena contains $N$ trees, each located at a point in the plane. A team chooses one tree and starts there. Whenever it moves from one tree to another it travels in a straight line. The team's score is the number of distinct trees it visits before returning to the tree it started from.

There is one rule: at every move the team must turn counterclockwise. That is, upon arriving at a tree, when heading to the next one it may rotate its heading to the left by strictly more than $0$ and strictly less than $180$ degrees. (Going straight, turning right, or reversing exactly backward are not allowed.)

Among all closed routes that obey this rule and return to the starting tree, you want to maximize the number of visited trees (the score). Given the positions of the trees, find the maximum achievable score.

Input

The first line contains the number of trees $N$ ( $3 \le N \le 100$ ).

Each of the next $N$ lines contains the coordinates of a tree: two real numbers $x$ , $y$ ( $-10^6 \le x, y \le 10^6$ ) separated by a space. Each coordinate is given with at most two digits after the decimal point.

No three trees lie on the same straight line.

Output

Print the maximum achievable score on the first line.

Examples3

Example 1
Input
```
5
0 0
1.5 -0.25
0 -1
-1 0.5
0.5 1
```
Expected output
```
4
```
Example 2
Input
```
3
0 0
10 0
0 10
```
Expected output
```
3
```
Example 3
Input
```
4
0 0
4 0
4 4
0 4
```
Expected output
```
4
```