এই সমস্যায়, আমাদেরকে 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 স্থানাঙ্কের সর্বোচ্চ এবং সর্বনিম্ন মান খুঁজে বের করতে হবে এর প্রতিবেশী পয়েন্টগুলির একটি বৈধ গণনার জন্য থাকতে পারে। এবং যদি কোন স্থানাঙ্ক বিদ্যমান থাকে যার একই 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
