ধরুন K ডাইমেনশন স্পেসে আমাদের n ভিন্ন বিন্দু আছে, n-এর মান রেঞ্জে (2, 105), এবং k-এর মান রেঞ্জে (1 থেকে 5)। আমাদের বিন্দুটি এমনভাবে নির্ধারণ করতে হবে যাতে ফলাফল বিন্দু থেকে n বিন্দুতে ম্যানহাটনের দূরত্বের যোগফল ন্যূনতম হয়।
P1(x1, y1) এবং P2(x2, y2) দুটি বিন্দুর মধ্যে ম্যানহাটনের দূরত্ব হল |x1 – x2| + |y1 – y2|। ধরুন মাত্রা হল 3, এবং তিনটি বিন্দু আছে যেমন (1, 1, 1), (2, 2, 2), (3, 3, 3), তাহলে আউটপুট হবে (2, 2, 2)।
এই সমস্যাটি সমাধান করার জন্য, আমাদের সমস্ত K ডাইমেনশনে পয়েন্টগুলি সাজাতে হবে এবং প্রতিটি k ডাইমেনশনের মধ্যম উপাদান থেকে আউটপুট পেতে হবে।
উদাহরণ
#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) //sort in all k dimension
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
