Cows

Time limit1sMemory limit128 MB

Summary

Given up to 10000 tree coordinates, find the largest convex polygon using any subset as corners, then output its area divided by 50 rounded down.

Level: Medium6 of 10
Topics: Geometry, Sorting, Array, Brute force
Solved: No attempts yet

Problem

Farmers want to save money by using the trees that grow on their land as fence posts, so they can build the largest possible pasture. You are given the locations of some trees. Consider the largest pasture (a convex polygon) that can be built using some or all of these trees as its corners. Not every tree has to be used.

What you must determine is how many cows can be placed in that pasture. It is well known that a cow needs at least $50$ square metres of pasture to survive. Therefore the answer is the area of the largest possible pasture divided by $50$ , rounded down.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10000$ ), the number of trees growing on the land. Each of the next $n$ lines contains the integer coordinates of one tree as two integers $x$ and $y$ separated by a space ( $-1000 \le x, y \le 1000$ ). One unit of coordinate corresponds to exactly one metre; for example, the distance between coordinates $(10, 11)$ and $(11, 11)$ is one metre.

Output

Output a single integer: the number of cows that can survive on the largest pasture you can construct.

Examples1

Example 1
Input
```
4
0 0
0 101
75 0
75 101
```
Expected output
```
151
```