マンハッタン距離の合計がC++で最小になるような点を見つけます

K次元空間にn個の異なる点があり、nの値が範囲（2、105）にあり、kの値が範囲（1〜5）にあるとします。結果の点からn点までのマンハッタン距離の合計が最小になるように点を決定する必要があります。

2点P1（x1、y1）とP2（x2、y2）の間のマンハッタン距離は| x1 –x2|です。 + | y1 –y2|。次元が3で、（1、1、1）、（2、2、2）、（3、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