ধরি K ডাইমেনশনাল স্পেসে nটি ভিন্ন পয়েন্ট আছে, n-এর মান (2, 10⁵) রেঞ্জে, এবং k-এর মান 1 থেকে 5। আমাদের সেটি পয়েন্ট বের করতে হবে যেন সেটি থেকে nটি পয়েন্ট পর্যন্ত ম্যানহ্যাটন দূরত্বের যোগফল ন্যূনতম হয়।
দুটি পয়েন্ট P1(x1, y1) এবং P2(x2, y2)-এর ম্যানহ্যাটন দূরত্ব হল |x1 - x2| + |y1 - y2|। ধরি ডাইমেনশন ৩, এবং তিনটি পয়েন্ট (1,1,1), (2,2,2), (3,3,3), তবে আউটপুট হবে (2,2,2)।
এটি সমাধান করতে সব K ডাইমেনশনে পয়েন্টগুলো সর্ট করে প্রতিটি ডাইমেনশনের মিডিয়ান (middle element) নিলেই হবে।
উদাহরণ কোড
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
void minimizeHanhattan(int n, int k, vector<vector<int> >& pointList) {
for (int i = 0; i < k; ++i) // সব k ডাইমেনশনে সর্ট
sort(pointList[i].begin(), pointList[i].end());
for (int i = 0; i < k; ++i)
cout << pointList[i][(ceil((double)n / 2) - 1)] << " ";
}
int main() {
int n = 4, k = 4;
vector<vector<int> > point = { { 1, 5, 2, 4 },
{ 6, 2, 0, 6 },
{ 9, 5, 1, 3 },
{ 6, 7, 5, 9 } };
minimizeHanhattan(n, k, point);
}
আউটপুট
2 2 3 6
