Đề bài
Chúng ta được cho N điểm trên mặt phẳng Descartes. Nhiệm vụ của chúng ta là tìm số lượng điểm tối thiểu cần loại bỏ để các điểm còn lại nằm về một phía của bất kỳ trục nào.
Nếu đầu vào cho trước là {(10, 5), (-2, -5), (13, 8), (-14, 7)} thì nếu loại bỏ (-2, -5) thì tất cả các điểm còn lại đều nằm phía trên trục hoành (X-axis).
Do đó câu trả lời là 1.
Thuật toán
1. Tìm số điểm ở tất cả các phía của trục hoành (X-axis) và trục tung (Y-axis) 2. Trả về giá trị nhỏ nhất từ cả hai
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; }
Kết quả
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