曼哈顿距离（Manhattan Distance）

在二维空间中，两个点 (x1, y1) 和 (x2, y2) 的 曼哈顿距离 是：

|x1 - x2| + |y1 - y2|

曼哈顿距离描述了在网格上行走的距离，限制只能水平或垂直移动。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

const int N = 1e5; // 最大点数限制
int x[N], y[N];     // 存储 x 和 y 坐标

int main() {
    int n;
    cin >> n;  // 输入点的数量

    // 输入 n 个点的坐标
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];  // 读取每个点的 x 和 y 坐标
    }

    // 对 x 坐标排序
    sort(x, x + n);

    // 对 y 坐标排序
    sort(y, y + n);

    // 通过调整 x 坐标使其从 0 开始，这一步实际上是为了后面更容易找到中位数
    for (int i = 0; i < n; i++) {
        x[i] -= i;  // 将 x[i] 减去索引，这样可以确保坐标调整为连续的
    }

    // 对调整后的 x 坐标进行排序
    sort(x, x + n);

    // 选取 x 和 y 的中位数作为目标坐标
    int midx = x[(n - 1) / 2];  // x 坐标的中位数
    int midy = y[(n - 1) / 2];  // y 坐标的中位数

    int sum = 0;

    // 计算所有点到 (midx, midy) 的曼哈顿距离之和
    for (int i = 0; i < n; i++) {
        sum += abs(midx - x[i]) + abs(midy - y[i]);
    }

    // 输出结果
    cout << sum << endl;

    return 0;
}