এই সমস্যায়, আমাদের N সংখ্যক পয়েন্ট দেওয়া আছে যা 2D প্লেনে অবস্থিত। আমাদের কাজ হল কমপক্ষে একটি পয়েন্ট উপরে, নিচে, বামে বা ডানে থাকা পয়েন্টের সংখ্যা বের করা।
আমাদের সব পয়েন্ট গুনতে হবে যেগুলোর কমপক্ষে একটি পয়েন্ট নিচের শর্তগুলোর যেকোনো একটি পূরণ করে।
উপরে পয়েন্ট − পয়েন্টটির 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
