Minimum Number of Points to Remove for Axis Alignment in C++

Problem statement

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.

If given input is {(10, 5), (-2, -5), (13, 8), (-14, 7)} then if we remove (-2, -5) then all remaining points are above X-axis.

Hence answer is 1.

Algorithm

1. Finds the number of points on all sides of the X-axis and Y-axis
2. Return minimum from both of them

Example

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct point{
   int x, y;
};
int minPointsToBeRemoved(point arr[], int n){
   int a = 0, b = 0, c = 0, d = 0;
   for (int i = 0; i < n; i++){
      if (arr[i].x >= 0)
         b++;
      else if (arr[i].x <= 0)
         a++;
      if (arr[i].y <= 0)
         d++;
      else if (arr[i].y >= 0)
         c++;
   }
   return min({a, d, c, b});
}
int main(){
   point arr[] = {{10, 5}, {-2, -5}, {13, 8}, {-14, 7}};
   cout << "Minimum points to be removed = " <<
   minPointsToBeRemoved(arr, SIZE(arr)) << endl;
   return 0;
}

Output

When you compile and execute the above program. It generates the following output −

Minimum points to be removed = 1