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) //सभी 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