New Year and Castle Construction
Contest: Hello 2020
Difficulty rating: 2500
Tags: combinatorics, geometry, math, sortings

Kiwon's favorite video game is now holding a new year event to motivate the users! The game is about building and defending a castle, which led Kiwon to think about the following puzzle.

In a 2-dimension plane, you have a set $$$s = \{(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\}$$$ consisting of $$$n$$$ distinct points. In the set $$$s$$$, no three distinct points lie on a single line. For a point $$$p \in s$$$, we can protect this point by building a castle. A castle is a simple quadrilateral (polygon with $$$4$$$ vertices) that strictly encloses the point $$$p$$$ (i.e. the point $$$p$$$ is strictly inside a quadrilateral).

Kiwon is interested in the number of $$$4$$$-point subsets of $$$s$$$ that can be used to build a castle protecting $$$p$$$. Note that, if a single subset can be connected in more than one way to enclose a point, it is counted only once.

Let $$$f(p)$$$ be the number of $$$4$$$-point subsets that can enclose the point $$$p$$$. Please compute the sum of $$$f(p)$$$ for all points $$$p \in s$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$5 \le n \le 2\,500$$$).

In the next $$$n$$$ lines, two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) denoting the position of points are given.

It is guaranteed that all points are distinct, and there are no three collinear points.

Output format:
Print the sum of $$$f(p)$$$ for all points $$$p \in s$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Example input:
5
-1 0
1 0
-10 -1
10 -1
0 3

Example output:
2

Example input:
8
0 1
1 2
2 2
1 3
0 -1
-1 -2
-2 -2
-1 -3

Example output:
40

Editorial:
Writers know of at least three different methods to approach this problem. The following approach is not the easiest one, but the most beautiful one in my opinion.
We will take the approach of calculating $$$\sum_{p \in S} f(p)$$$ itself, instead of computing each term independently. Consider all 5-point subsets out of $$$n$$$ points. As no three points are collinear, there are three cases:
• Convex hull has 3 vertices. We denote the number of such subsets as $$$x_3$$$. In this case, the two vertices strictly inside the hull can be enclosed by other vertices (Draw a straight line connecting those two points, and extend the non-intersected edge toward one of them, to enclose the other). The contribution to the answer is $$$2 \times x_3$$$.
• Convex hull has 4 vertices. We denote the number of such subsets as $$$x_4$$$. In this case, the point not in the hull can obviously be enclosed, but the points on the hull cannot be. The contribution to the answer is $$$x_4$$$.
• Convex hull has 5 vertices. We denote the number of such subsets as $$$x_5$$$. In this case, no point can be enclosed. The contribution to the answer is 0.
We can see that the answer we want is $$$2x_3 + x_4$$$. On the other hand, $$$x_3 + x_4 + x_5 = \binom{n}{5}$$$, by definition.
Now here comes the magic. If we can compute the value $$$3x_3 + 4x_4 + 5x_5$$$ somehow, then the answer can be easily derived. It turns out this can be done in $$$O(n^2 \log n)$$$ time, by exploiting the form $$$\sum_{i = 3}^{5} i \times x_i$$$. This quantity corresponds to the sum of edges of the convex hull for all 5-point subsets. Then, we can instead try to enumerate all $$$O(n^2)$$$ possible edges, and count the number of 5-point subsets that contain each edge.
Consider each edge as being directed. In other words, we'll only consider edges where $$$(i, j)$$$ are adjacent in the counterclockwise direction. Then the number of possible 5-point subsets is simply $$$\binom{l_{i, j}}{3}$$$, where $$$l_{i, j}$$$ is the number of vertices that lies left to the directed vector $$$(i, j)$$$. $$$l_{i, j}$$$ can be obviously counted in $$$O(n^3)$$$ time. If we perform an angular sort for fixed $$$i$$$, we can optimize this to $$$O(n^2 \log n)$$$ time by using two pointers.