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

Trong bài toán này, chúng ta có N điểm nằm trong một 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, bên trái hoặc bên phải của nó .

Chúng ta cần đếm tất cả các điểm có ít nhất 1 điểm thỏa mãn bất kỳ điều kiện nào dưới đây.

Trỏ phía trên nó - Điểm sẽ có cùng tọa độ X và tọa độ Y hơn giá trị hiện tại của nó một tọa độ.

Trỏ bên dưới nó - Điểm sẽ có cùng tọa độ X và tọa độ Y nhỏ hơn một tọa độ so với giá trị hiện tại của nó.

Trỏ sang trái - Điểm sẽ có cùng tọa độ Y và tọa độ X nhỏ hơn giá trị hiện tại của nó một điểm.

Trỏ sang phải - Điểm sẽ có cùng tọa độ Y và tọa độ X hơn giá trị hiện tại của nó một điểm.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta cần đưa từng điểm tạo thành 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ủa nó có thể có để đếm hợp lệ. Và nếu tồn tại bất kỳ tọa độ nào có cùng tọa độ X và giá trị của Y nằm trong phạm vi. Chúng tôi sẽ tăng số điểm. Chúng tôi sẽ lưu trữ số lượng trong một biến và trả về.

Ví dụ

Hãy lấy một ví dụ để hiểu vấ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);
}

Đầu ra

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