이 문제에서는 2D 평면에 있는 N개의 점이 제공됩니다. 우리의 임무는 위, 아래, 왼쪽 또는 오른쪽에 최소 1개의 점이 있는 점의 수를 찾는 것입니다. .
아래 조건 중 하나를 충족하는 1점 이상의 모든 점수를 계산해야 합니다.
위를 가리킴 − 점은 동일한 X 좌표를 가지며 Y 좌표는 현재 값보다 하나 더 큽니다.
아래를 가리킴 − 점은 동일한 X 좌표를 가지며 Y 좌표는 현재 값보다 하나 작습니다.
왼쪽 지점 − 점은 동일한 Y 좌표를 가지며 X 좌표는 현재 값보다 하나 작습니다.
오른쪽을 가리킴 − 점은 동일한 Y 좌표를 가지며 X 좌표는 현재 값보다 하나 더 큽니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input : arr[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}}
Output :1 솔루션 접근 방식
이 문제를 해결하려면 평면에서 각 점을 가져와서 유효한 개수에 대해 인접 점이 가질 수 있는 X 및 Y 좌표의 최대값과 최소값을 찾아야 합니다. 그리고 X좌표가 같고 Y값이 범위 안에 있는 좌표가 존재한다면. 포인트 수를 늘리겠습니다. 카운트를 변수에 저장하고 반환합니다.
예시
문제를 이해하기 위해 예를 들어보겠습니다.
#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