Let N be the number of points. We can see that (the number of finite regions) = (the number of crossings) + (the number of components) — N. Since the number of components is a constant (unless we make really stupid choice of directions), we want to maximize the number of crossings.

Now, let's convert the coordinates, and assume the following:

• Half-lines go to left or down from each point.
• Each coordinate is between 0 and N, and of the form "integer + 0.5".

We want to color the points red and blue, and maximize the number of pairs of red point R and blue point B such that x(R) < x(B) and y(R) > y(B).

Here, in one optimal solution, we can prove that their is a shortest path from (0, 0) to (N, N) that splits the square [0, N] × [0, N] into two regions, such that in one region all points are red and in the other region all points are blue. Now it's not hard to come up with an O(N²) DP.