Maximum Convex Fence Posts

Farmer John has N fence posts, each at unique integer coordinates ( (x_i, y_i) ) where (5 \le N \le 250) and (1 \le x_i, y_i \le 1000). He wishes to build an aesthetically pleasing fence by selecting as many posts as possible as the vertices of a convex polygon.

A polygon is convex if for every three consecutive vertices (a, b, c) (taken in cyclic order) the turn is strictly counterclockwise, i.e. (\text{cross}(b-a, c-b) > 0) where the cross product is defined by (\text{cross}(a,b,c)= (b_x-a_x)(c_y-b_y) - (b_y-a_y)(c_x-b_x)) in (\LaTeX) format.

Given that no three fence posts are collinear, determine the maximum number of fence posts that can be chosen so that, when connected in order (with the last connected back to the first), they form a convex polygon.

inputFormat

The first line contains an integer (N), the number of fence posts. Each of the next (N) lines contains two space‐separated integers (x_i) and (y_i) representing the coordinates of a fence post.

outputFormat

Output a single integer representing the largest number of fence posts that can be used to form a convex polygon.

sample

5
1 1
2 3
3 2
4 4
5 1

4