एक बिंदु खोजें जैसे कि मैनहट्टन दूरियों का योग C++ में न्यूनतम हो

मान लीजिए हमारे पास 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