Tìm số điểm có ít nhất 1 điểm ở trên, dưới, trái hoặc phải trong C++

Trong bài toán này, chúng ta được cho N điểm nằm trên mặt phẳng 2D. Nhiệm vụ của chúng ta là tìm số điểm có ít nhất 1 điểm ở trên, dưới, trái hoặc phải của nó.

Ta cần đếm tất cả điểm thỏa mãn ít nhất 1 trong các điều kiện sau:

Điểm ở trên nó − Điểm có cùng tọa độ X và tọa độ Y lớn hơn 1 đơn vị.

Điểm ở dưới nó − Điểm có cùng tọa độ X và tọa độ Y nhỏ hơn 1 đơn vị.

Điểm ở trái nó − Điểm có cùng tọa độ Y và tọa độ X nhỏ hơn 1 đơn vị.

Điểm ở phải nó − Điểm có cùng tọa độ Y và tọa độ X lớn hơn 1 đơn vị.

Hãy xem ví dụ sau để hiểu bài toán:

Input : arr[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}} Output :1

Phương pháp giải

Để giải bài toán, ta lấy từng điểm trên mặt phẳng và tìm giá trị lớn nhất và nhỏ nhất của tọa độ X và Y mà các điểm lân cận có thể có để đếm hợp lệ. Nếu tồn tại tọa độ nào có cùng X và giá trị Y nằm trong khoảng. Ta tăng biến đếm điểm. Lưu đếm trong biến và trả về.

Ví dụ

Hãy xem ví dụ để hiểu bài toán

#include <bits/stdc++.h> using namespace std; #define MX 2001 #define OFF 1000 struct point {    int x, y; }; int findPointCount(int n, struct point points[]){    int minX[MX];    int minY[MX];    int maxX[MX] = { 0 };    int maxY[MX] = { 0 };    int xCoor, yCoor;    fill(minX, minX + MX, INT_MAX);    fill(minY, minY + MX, INT_MAX);    for (int i = 0; i < n; i++) {       points[i].x += OFF;       points[i].y += OFF;       xCoor = points[i].x;       yCoor = points[i].y;       minX[yCoor] = min(minX[yCoor], xCoor);       maxX[yCoor] = max(maxX[yCoor], xCoor);       minY[xCoor] = min(minY[xCoor], yCoor);       maxY[xCoor] = max(maxY[xCoor], yCoor);    }    int pointCount = 0;    for (int i = 0; i < n; i++) {       xCoor = points[i].x;       yCoor = points[i].y;       if (xCoor > minX[yCoor] && xCoor < maxX[yCoor])          if (yCoor > minY[xCoor] && yCoor < maxY[xCoor])             pointCount++;    }    return pointCount; } int main(){    struct point points[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}};    int n = sizeof(points) / sizeof(points[0]);    cout<<"The number of points that have atleast one point above, below, left, right is "<<findPointCount(n, points); }

Kết quả

The number of points that have atleast one point above, below, left, right is 1