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