Tìm một điểm sao cho tổng khoảng cách Manhattan là nhỏ nhất trong C ++

Giả sử chúng ta có n điểm khác nhau trong không gian chiều K, giá trị của n nằm trong khoảng (2, 105) và giá trị của k trong khoảng (1 đến 5). Chúng ta phải xác định điểm sao cho tổng khoảng cách Manhattan từ điểm kết quả đến n điểm là nhỏ nhất.

Khoảng cách Manhattan giữa hai điểm P1 (x1, y1) và P2 (x2, y2) là | x1 - x2 | + | y1 - y2 |. Giả sử kích thước là 3 và có ba điểm như (1, 1, 1), (2, 2, 2), (3, 3, 3), thì đầu ra sẽ là (2, 2, 2).

Để giải quyết vấn đề này, chúng ta phải sắp xếp các điểm theo tất cả K kích thước và lấy kết quả từ các phần tử ở giữa của mỗi kích thước k.

Ví dụ

#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);
}

Đầu ra

2 2 3 6