Suppose we have $2 \leq n \leq 300$ points $p_i$ with coordinates $(x_i, y_i), \ x_i, y_i \in \mathbb{Z}$. Among all partitions of the set into two nonvoid subsets, how many are induced by a partition by a straight line splitting the plane into 2 halfplanes. We're allowed to use some programming.
I've spent hours to do it, but i got nothing.
In this answer, we'll assume that the points are in general position, i.e., that no three points line on the same line. See the end for the changes when the points are not in general position. With this assumption, then the number of ways to split a collection of points is independent of the arrangement of points.
We will also assume that all points have distinct $x$ and $y$ coordinates. This is not a restrictive extra condition since a small rotation will result in this case without changing the relative position of lines and points.
To answer this question, I'll use point-line duality. The duality transformation takes lines to points and points to lines:
The point $p=(p_x,p_y)$ to the line $y=p_xx-p_y$. The corresponding line is called a dual point and is denoted $p^\ast$.
The line $y=mx+b$ to the point $(m,-b)$. The corresponding point is called a dual line and if the original line is $\ell$, then the dual line is denoted $\ell^\ast$.
One can easily check that these operations are inverses of each other. There are many nice properties of the dual, but the one that we need here is that if $\ell$ is a line and $\{p_1,\dots,p_k\}$ are points below $\ell$, then $\ell^\ast$ is a point and each of the lines $\{p_1^\ast,\dots,p_k^\ast\}$ are above $\ell^\ast$.
In your case, if you take each of your points $\{p_1,\dots,p_n\}$ and look at the dual points (i.e., lines) $\{p_1^\ast,\dots,p_n^\ast\}$, these lines divide up the plane into regions. Note that:
The general position assumption implies that now three dual points have a common intersection.
The assumption that all points have distinct $x$ coordinates implies that the slops of the dual points are all different.
Let $q^\ast$ be a point in a region determined by the dual points, i.e., in their complement. Then the points above the corresponding line $q$ in the primal (i.e., the original plane) correspond to the lines below $q^\ast$ in the dual. Since this doesn't change in a region (i.e., connected component) determined by the dual points,
There is a bijection between connected regions in the dual and equivalence classes of lines with the same subsets of points below the line.
The next step is to count the number of regions formed by the dual points. We can do this using the Euler characteristic of a sphere. By putting a point at infinity, we can embed these dual points (lines) as great circles, which all intersect at infinity. For the Euler characteristic for a sphere, we know that $$\#V-\#E+\#F=2.$$ Since the lines all have distinct slopes, they all intersect, resulting in $$ \#V=\binom{n}{2}+1. $$ The $+1$ comes from the point at infinity. Since every line intersects every other line (and all $n-1$ lines intersect any fixed line), there are $n$ edges per line, resulting in $$ \#E=n^2. $$ Putting this all together, we have $$ 2=\binom{n}{2}+1-n^2+\#F $$ or that the number of regions is $$ \#F=1+n^2-\frac{n^2-n}{2}=1+\frac{n^2}{2}+\frac{n}{2}. $$ Now, this does not quite answer your question because unbounded regions over-count some of the partitions (more details are below). In fact, $n$ of the partitions are over-counted. Therefore, we need to subtract $n$ from our count to get that the number of ways to split the data set into two subsets by lines (but allowing for an empty set) is $$ 1+\frac{n^2}{2}+\frac{n}{2}-n=1+\binom{n}{2}. $$ Finally, we need to subtract the split of the entire set and the empty set, to get that the number of partitions is always $$ \binom{n}{2}. $$
Now, let's take a look this over-counting business. The over-counting comes about because there are times when there are pairs of lines $\{\ell_1,\ell_2\}$ that are nearly vertical and the set of points below $\ell_1$ is equal to the set of points above $\ell_2$. These over-counts correspond to the unbounded regions in the dual setting. Alternatively, these correspond to vertical lines between points of the original data set (including the vertical line to the far right of the data set, which is identified with the vertical line to the far left of the data set). There are $n$ such lines, so there are $2n$ unbounded regions which are identified in pairs.
Note that if the points are not in general position, then the number of vertices in the dual can change. In particular, suppose that there are lines $\ell_1,\dots,\ell_k$ so that line $\ell_i$ has $n_i\geq 3$ points on it. In this case, the dual points on this line don't have $\binom{n_i}{2}$ different intersection points, they have all been combined into into a single point. Then, the number of points counted above must be reduced by $$ \sum_{i=1}^k\left(\binom{n_i}{2}-1\right)=-k+\sum_{i=1}^k\binom{n_i}{2}. $$ Then, the rest of the argument proceeds as above (including the over-count).