Gregor and the Odd Cows (Hard)

Description:

Input:

The first line contains the integer $$$n$$$ ($$$3 \le n \le 6000$$$), the number of fence posts which Gregor can choose to form the vertices of a fence.

Each of the next $$$n$$$ line contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x,y \le 10^7$$$, where $$$(x,y)$$$ is the coordinate of a fence post. All fence posts lie at distinct coordinates. No three fence posts are on the same line.

Output:

Print a single integer, the number of interesting fences. Two fences are considered different if they are constructed with a different set of three fence posts.

Sample Input:

3
0 0
2 0
0 4

Sample Output:

1

Sample Input:

4
1 8
0 6
5 2
5 6

Sample Output:

1

Sample Input:

10
170 59
129 54
5 98
129 37
58 193
154 58
24 3
13 138
136 144
174 150

Sample Output:

29

Note:

In the first example, there is only $$$1$$$ fence. That fence is interesting since its area is $$$4$$$ and there is $$$1$$$ enclosed cow, marked in red.

In the second example, there are $$$4$$$ possible fences. Only one of them is interesting however. That fence has an area of $$$8$$$ and $$$5$$$ enclosed cows.