Let's find a convex hull. If there are both colors occurring in the hull then we can also find two neighbouring (adjacent) points with different color. Then we can match them and remove. Maybe it's not true that both colors occurring in the hull. Let's assume that vertices on the hull are all red. It turns out that then we are able to divide points into two smaller sets with one vertical cut.

Let's iterate over points in the order of increasing x. Let r and b denote the number of red and the number of blue points respectively. As we iterate over points we must keep value r - b. Because of the assumption about red points on the convex hull, we know that after the leftmost point we have r - b = 1 because the first point is red. And the last point is red so r - b =  - 1 at the end. As we iterate we change r - b by  + 1 or  - 1 so in some moment we must get exactly 0. It allows us to divide a set of points into two separate sets and we can solve smaller problems recursively.

Another approach to this problem is to find a matching between two point sets with minimal sum of distances between matched points. You can do that with either mincostmaxflow or hungarian algorithm in O(n^3). Now, suppose that two line segments a1-b1 and a2-b2 intersect in the optimal matching. But that means that they are two diagonals of convex quadrilateral a1-a2-b1-b2, so by triangle inequality, |a1-b2|+|a2-b1|<|a1-b1|+|a2-b2|, which contradicts with matching optimality.