Largest Fence

Time limit2sMemory limit128 MB

Summary

Given N grid points with no three collinear, find the size of the largest subset whose points form the vertices of a convex polygon.

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

Problem

A farmer has bought $N$ fence posts and wants to arrange some of them into a good-looking fence. The nicest fences are convex polygons whose vertices are fence posts.

The field is a grid. Post $i$ stands at integer coordinates $(x_i, y_i)$ with $1 \le x_i \le 1000$ and $1 \le y_i \le 1000$ . All posts are at distinct positions, and no three posts are collinear.

Choose a subset of the posts to be the vertices of a single convex polygon, so that every chosen post is a corner (vertex) of that polygon. What is the largest number of posts such a convex polygon can use?

Constraints

$5 \le N \le 250$
$1 \le x_i, y_i \le 1000$
No three posts lie on a common line.

Input

The first line contains a single integer $N$ .
Each of the next $N$ lines contains two space-separated integers $x_i$ and $y_i$ : the coordinates of post $i$ .

Output

Print a single integer: the maximum number of posts that can form the vertices of a convex polygon.

Hint

For the sample field, the largest convex polygon is the pentagon with vertices $(2,3)$ , $(3,2)$ , $(5,1)$ , $(5,5)$ , $(1,5)$ . The remaining post at $(1,1)$ cannot be added without making the polygon non-convex, so the answer is $5$ .

Examples3

Example 1
Input
```
6
5 5
2 3
3 2
1 5
5 1
1 1
```
Expected output
```
5
```
Example 2
Input
```
5
3 1
6 3
5 7
2 7
1 3
```
Expected output
```
5
```
Example 3
Input
```
5
1 1
1 11
11 11
11 1
4 6
```
Expected output
```
4
```