Home > Article > Backend Development > Find the number of points that have at least one point above, below, left or right of it in C++
In this problem, we are given N points located on a 2D plane. Our task is to find the number of points that have at least 1 point above, below, to the left or to the right of it.
We need to calculate all points that have at least 1 point 1 point that satisfies any of the following conditions.
The point above it− The point will have the same X coordinate and a Y coordinate 1 greater than its current value. p>
The point below it− The point will have the same X coordinate and a Y coordinate 1 less than its current value.
The point to its left− The point will have the same Y coordinate and an X coordinate 1 less than its current value.
Point to the right of this point − This point will have the same Y coordinate and X coordinate 1 greater than the current value.
Let us take an example to understand this problem,
Input : arr[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}} Output :1
In order to solve this problem, we need to take out each point and find the maximum and minimum values of X and Y coordinates that its neighboring points can have for valid counting. If there are any coordinates with the same X coordinate and a Y value within that range. We will add points. We store the count in a variable and return it.
Let us take an example to understand the problem
#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); }
The number of points that have atleast one point above, below, left, right is 1
The above is the detailed content of Find the number of points that have at least one point above, below, left or right of it in C++. For more information, please follow other related articles on the PHP Chinese website!