最小曼哈顿距离

解题思路:

首先可以发现，要使得所有点到一个点的曼哈顿距离之和最小，这个点必然是所有点的中心点。因此，我们只需要枚举所有可能的中心点，计算每个中心点到所有点的曼哈顿距离之和，取最小值即可。

具体实现时，我们可以先找到所有点的最大横坐标、最小横坐标、最大纵坐标、最小纵坐标，然后枚举所有可能的中心点，计算每个中心点到所有点的曼哈顿距离之和，并取最小值。

注意事项:

参考代码:

#include<stdio.h>

int max(int x, int y)

{

return x > y ? x : y;

}

int min(int x,int y)

{

return x < y ? x : y;

}

int main()

{

int a[10000] = { 0 }, b[10000] = { 0 };

int n,i,j,k;

scanf_s("%d", &n);

for (i = 0; i < n; i++)

{

scanf_s("%d %d", &a[i], &b[i]);

}

int min_x=a[0],max_x=a[0], max_y=b[0],min_y=b[0];

for (i = 1; i < n; i++)

{

max_x = max(max_x, a[i]);

max_y = max(max_y, b[i]);

min_x = min(min_x, a[i]);

min_y = min(min_y, b[i]);

}

int m=1e9;

for (i = min_x; i <= max_x; i++)

for (j = min_y; j <= max_y; j++)

{ 

int sum = 0;

for (k = 0; k < n; k++)

{

sum += abs(i - a[k]) + abs(j - b[k]);

}

m = min(m, sum);

}

printf("%d\n", m);

return 0;

}