Satanic Panic
Contest: Forethought Future Cup - Elimination Round
Difficulty rating: 2900
Tags: dp, geometry

You are given a set of $$$n$$$ points in a 2D plane. No three points are collinear.

A pentagram is a set of $$$5$$$ points $$$A,B,C,D,E$$$ that can be arranged as follows.  Note the length of the line segments don't matter, only that those particular intersections exist.

Count the number of ways to choose $$$5$$$ points from the given set that form a pentagram.

Input format:
The first line contains an integer $$$n$$$ ($$$5 \leq n \leq 300$$$) — the number of points.

Each of the next $$$n$$$ lines contains two integers $$$x_i, y_i$$$ ($$$-10^6 \leq x_i,y_i \leq 10^6$$$) — the coordinates of the $$$i$$$-th point. It is guaranteed that no three points are collinear.

Output format:
Print a single integer, the number of sets of $$$5$$$ points that form a pentagram.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
A picture of the first sample:  A picture of the second sample:  A picture of the third sample:

Example input:
5
0 0
0 2
2 0
2 2
1 3

Example output:
1

Example input:
5
0 0
4 0
0 4
4 4
2 3

Example output:
0

Editorial:
Originally, I only had an $$$O(n^4)$$$ solution, but [user:y0105w49] recognized an easy solution with bitsets and helped me find an $$$O(n^3)$$$ solution instead.
We do this by counting out bad configurations. There are initially $$$\binom{n}{5}$$$ tuples of $$$5$$$ points, and we want to subtract out bad configurations. There are two classes of bad configurations. One is a point in a convex quadrilateral. The other is a pair of points inside a triangle. If we look at the first class of bad configurations, we can notice it has two instances of "point in a triangle", and if we look at the second class, it has four instances of "point in a triangle". See the following image for more details:
Let's precompute for each number $$$i$$$, the number of triangles from the chosen set that contains $$$i$$$ points inside its interior. Let this number be $$$f_i$$$. This can be found using bitsets in $$$O(n^4 / 64)$$$ time, or some other geometric method in $$$O(n^3)$$$ time.
First, we can subtract out $$$\sum i\cdot f_i\cdot(n-4) / 2$$$. This removes subtracts all instances of the first class of bad configuration, but double subtracts instances of the second class of bad configurations. To fix that, we can add back $$$\sum \binom{i}{2} f_i$$$.
The final formulas only take $$$O(n)$$$ time to evaluate, so the time is mostly spent computing the $$$f$$$ values which is $$$O(n^3)$$$ time.
There is also another approach using some angle sweeps that I found later (though a bit harder to explain and to implement). The main idea is to fix the bottom point of the pentagram as well as the third and fourth points. Then, it reduces to counting the number of points that lie in some intersection of half planes. To do it efficiently, if we fix the first and third points, then we can do an angle sweep to efficiently count the number of points that could be the second point as we are iterating through the fourth point (and symmetrically we can do this to count the fifth point and multiply the two together). We can precompute these numbers to get a runtime of $$$O(n^3 log n)$$$.
A third solution from Scott: the goal is to find the number of convex pentagons. We will do this through constructive DP. Take all directed segments between points and sort them by angle. Then, maintain array $$$dp[i][j][k]$$$, the number of polylines that start at vertex 𝑖, end at vertex 𝑗, contain 𝑘 segments, and only make clockwise turns. Loop over each directed segment in order and update the DP array accordingly. Each pentagon has exactly one traversal that satisfies the above constraints, so the answer is just the sum of all $$$dp[i][i][5]$$$.