407564: GYM102829 K Doggos in Data

Generating data for contests is very tedious work, and Viraj often gets bored doing it. During his breaks, he surfs various subreddits for pictures of the floofiest doggos. He also likes to ask his friends, including the other UTPC officers, for pictures of their pets to sneak into the test data he generates for geometry problems. However, Viraj's recent requests have been left on read, and he is infuriated at the lack of responses. He decides to kidnap ALL of their pets and store them at a remote location until enough photos can be amassed (some may even be posted on Reddit for karma). However, being a man of honor, Viraj decides to allow the officers a chance to get their beloved pooches back by solving his latest contest problem.

In each test case, there are $$$N$$$ lattice points on the Cartesian Plane such that no three points are collinear. The officers must consider every possible subset of the $$$N$$$ points, calculate the number of points in the convex hull of that subset, and add the sizes of the hulls together. This sum modulo $$$10^9+7$$$ can be decoded into a set of coordinates indicating the pets' location. The only issue is that all the officers hate geometry, so you need to help them out!

The first line of input contains a single positive integer $$$N$$$ ($$$1 \leq N \leq 300$$$) representing the number of points. The next $$$N$$$ lines of input contain two space separated nonnegative integers $$$x$$$ and $$$y$$$ ($$$0 \leq x, y \leq 10^6$$$) representing the coordinates of each point.

Output a single integer representing the sum of convex hull sizes over all subsets of points modulo $$$10^9+7$$$.

7
3 6
17 15
13 15
6 12
9 1
2 7
10 19

418

3
0 0
0 1
1 0

12

The size of the convex hull of a subset of less than 3 points is simply the size of the subset.