曼哈顿距离与切比雪夫距离

曼哈顿距离为 \(|x1-y1| + |x2-y2|\) 。

切比雪夫距离为 \(\max(|x1-y1|,|x2-y2|)\) 。

一个点 \((x,y)\) 的坐标变为 \((x+y,x-y)\) 后，原坐标系中曼哈顿距离 \(=\) 新坐标系中切比雪夫距离。

一个点 \((x,y)\) 的坐标变为 \((\dfrac{x+y}{2},\dfrac{x-y}{2})\) 后，原坐标系中的切比雪夫距离为新坐标系中的曼哈顿距离。

证明显然。

切比雪夫距离在计算的时候需要取 \(\max\) ，转化成曼哈顿距离可以规避掉这东西。

P3964 [TJOI2013]松鼠聚会

给定 \(n\) 个点，要求找到一个点使其他点到这个点的切比雪夫距离和最小。

\(1 \le n\le 1e5\)

发现知道结论之后这东西就是一个裸题，然后直接维护就好了。

然后转成曼哈顿距离时，坐标要除二，于是先整体乘 \(2\) ，最后答案除 \(2\) 就好了。

// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
// Problem: P3964 [TJOI2013]松鼠聚会
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3964
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// The Author : Pitiless0514
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
using namespace std;
#define int long long
#define pir pair 
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
#define vector  vec
#define unsigned long long u32
inline int min(int x,int y) { return (x < y) ? x : y;}
inline int max(int x,int y) { return (x > y) ? x : y;}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
}; //unordered_map
#define unordered_map  umap
#define outend() flush()
#define randnum(mod) rand2() % mod + 1
namespace IO {
  int len = 0;
  char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
  #define gh()                                                                   \
    (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),         \
    (iS == iT ? EOF : *iS++) : *iS++)
  inline int read() {
    char ch = gh();
    int x = 0;
    char t = 0;
    while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
    while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
    return t ? -x : x;
  }
  inline void putc(char ch) { out[len++] = ch; }
  template  inline void write(T x) {
    if (x < 0) putc('-'), x = -x;
    if (x > 9) write(x / 10);
    out[len++] = x % 10 + 48;
  }
  string getstr(void) {
    string s = "";
    char c = gh();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = gh();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF))s.push_back(c), c = gh();
    return s;
  }
  void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putc(str[i]);
    return;
  }
  inline void flush() {
    fwrite(out, 1, len, stdout);
    len = 0;
  }
} // namespace IO by Macesuted
using IO::flush;
using IO::getstr;
using IO::putc;
using IO::putstr;
using IO::read;
using IO::write;
const int N = 2e6;
int n, x[N], y[N], sx[N], sy[N];
struct node { int x, y; } a[N], b[N];
int cmp1( node x, node y ) { return x.x < y.x; }
int cmp2( node x, node y ) { return x.y < y.y; }
int calc( int id ) {
  int ans = 0, pos;
  pos = lower_bound(x + 1, x + n + 1, b[id].x) - x;
  ans += (b[id].x * (pos - 1) - sx[pos - 1] + sx[n] - sx[pos - 1] - b[id].x * (n - pos + 1));
  pos = lower_bound(y + 1, y + n + 1, b[id].y) - y;
  ans += (b[id].y * (pos - 1) - sy[pos - 1] + sy[n] - sy[pos - 1] - b[id].y * (n - pos + 1));
  return ans;
}
signed main () {
  n = read();
  for(int i = 1; i <= n; i++) {
    a[i].x = read(), a[i].y = read();
    b[i].x = a[i].x + a[i].y;
    b[i].y = a[i].x - a[i].y;
  }
  sort(b + 1, b + n + 1, cmp2);
  for(int i = 1; i <= n; i++) {
    y[i] = b[i].y;
    sy[i] = sy[i - 1] + y[i];
  }
  sort(b + 1, b + n + 1, cmp1);
  for(int i = 1; i <= n; i++) {
    x[i] = b[i].x;
    sx[i] = sx[i - 1] + x[i];
  }
  int ans = -1;
  for(int i = 1; i <= n; i++) {
    ans =  (ans < 0 ? calc(i) : min(ans, calc(i)));
  }
  cout << ans / 2 << "\n";
  return 0;
}