We are given n points in a Cartesian plane. Our task is to find the minimum number of points that should be removed in order to get the remaining points on one side of any axis.
Input : 4 1 1 2 2 -1 -1 -2 2 Output : 1 Explanation : If we remove (-1, -1) then all the remaining points are above x-axis. Thus the answer is 1. Input : 3 1 10 2 3 4 11 Output : 0 Explanation : All points are already above X-axis. Hence the answer is 0.
This problem is a simple example of constructive brute force algorithm on Geometry. The solution can be approached simply by finding the number of points on all sides of the X-axis and Y-axis. The minimum of this will be the answer.