इस समस्या में, हमें N बिंदु दिए गए हैं जो एक 2D तल में स्थित हैं। हमारा कार्य उन बिंदुओं की संख्या ज्ञात करना है जिनके ऊपर, नीचे, बाएँ या दाएँ कम से कम 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 का मान सीमा में है। हम पॉइंट काउंट बढ़ाएंगे। हम गिनती को एक वेरिएबल में स्टोर करेंगे और उसे वापस कर देंगे।
उदाहरण
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं
#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. है