इस समस्या में, हमें N बिंदु दिए गए हैं जो एक 2D प्लेन में स्थित हैं। हमारा कार्य उन बिंदुओं की संख्या ज्ञात करना है जिनके ऊपर, नीचे, बाएं या दाएं कम से कम 1 बिंदु हो।
हमें उन सभी बिंदुओं को गिनना है जिनके पास कम से कम 1 बिंदु हो जो नीचे दी गई किसी भी शर्त को संतुष्ट करता हो।
इसके ऊपर बिंदु - बिंदु का वही X निर्देशांक होगा और Y निर्देशांक इसके वर्तमान मान से एक अधिक होगा।
इसके नीचे बिंदु - बिंदु का वही X निर्देशांक होगा और Y निर्देशांक इसके वर्तमान मान से एक कम होगा।
इसके बाएं बिंदु - बिंदु का वही Y निर्देशांक होगा और X निर्देशांक इसके वर्तमान मान से एक कम होगा।
इसके दाएं बिंदु - बिंदु का वही Y निर्देशांक होगा और X निर्देशांक इसके वर्तमान मान से एक अधिक होगा।
उदाहरण से समझते हैं:
इनपुट: arr[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}} आउटपुट: 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
