Số điểm tối thiểu cần loại bỏ để có được các điểm còn lại trên một phía của trục bằng cách sử dụng C ++.

Tuyên bố vấn đề

Chúng tôi cho N điểm trong một mặt phẳng Descartes. Nhiệm vụ của chúng ta là tìm số điểm tối thiểu cần được loại bỏ để có được các điểm còn lại trên một phía của bất kỳ trục nào.

Nếu đầu vào đã cho là {(10, 5), (-2, -5), (13, 8), (-14, 7)} thì nếu chúng ta loại bỏ (-2, -5) thì tất cả các điểm còn lại đều nằm trên X -axis.

Do đó, câu trả lời là 1.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum points to be removed = 1