Description

草原上住着一群小松鼠，每个小松鼠都有一个家。时间长了，大家觉得应该聚一聚。但是草原非常大，松鼠们都很头疼应该在谁家聚会才最合理。

每个小松鼠的家可以用一个点 \((x,y)\) 表示，两个点的距离定义为点 \((x,y)\) 和它周围的 \(8\) 个点 \((x-1,y)\),\((x+1,y)\),\((x,y-1)\),\((x,y+1)\),\((x-1,y+1)\),\((x-1,y-1)\),\((x+1,y+1)\),\((x+1,y-1)\) 距离为 \(1\)。

Input

第一行是一个整数 \(N\)，表示有多少只松鼠。接下来 \(N\) 行，第 \(i\) 行是两个整数 \(x\) 和 \(y\)，表示松鼠 \(i\) 的家的坐标。

Output

一个整数，表示松鼠为了聚会走的路程和最小是多少。

Sample Input

6-4 -1-1 -22 -40 20 35 -2

60 02 0-5 -22 -2-1 24 0

Sample Output

20

15

HINT

\(0 ≤ N ≤ 100000, −10^9 ≤ x, y ≤ 10^9\)

Solution

\((x_1,y_1)\) 与 \((x_2,y_2)\) 两点的曼哈顿距离为

\[ |x_1-x_2|+|y_1-y_2| \]

切比雪夫距离为

\[ \max(|x_1-x_2|,|y_1-y_2|) \]

曼哈顿距离转切比雪夫距离：

\[ (x,y) \rightarrow (x+y,x-y) \]

切比雪夫距离转曼哈顿距离：

\[ (x,y) \rightarrow \left(\frac{x+y}{2},\frac{x-y}{2}\right) \]

Code

#include 
    
     #include 
     
      const int N = 100005;typedef long long LL;struct Pair { int x, y, idx; } a[N];LL sx[N], sy[N], px[N], py[N], ans = 1e18;int read() {    int x = 0, f = 1; char c = getchar();    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();    return x * f;}bool cmp1(Pair a, Pair b) { return a.x < b.x; }bool cmp2(Pair a, Pair b) { return a.y < b.y; }int main() {    int n = read();    for (int i = 1, x, y; i <= n; ++i)        x = read(), y = read(), a[i].x = x + y, a[i].y = x - y;    std::sort(a + 1, a + n + 1, cmp1);    a[1].idx = 1;    for (int i = 2; i <= n; ++i) {        sx[i] = sx[i - 1] + (i - 1LL) * (a[i].x - a[i - 1].x), a[i].idx = i;        px[n - i + 1] = px[n - i + 2] + (i - 1LL) * (a[n - i + 2].x - a[n - i + 1].x);    }    std::sort(a + 1, a + n + 1, cmp2);    for (int i = 2; i <= n; ++i) {        sy[i] = sy[i - 1] + (i - 1LL) * (a[i].y - a[i - 1].y);        py[n - i + 1] = py[n - i + 2] + (i - 1LL) * (a[n - i + 2].y - a[n - i + 1].y);    }    for (int i = 1; i <= n; ++i)        ans = std::min(ans, px[a[i].idx] + sx[a[i].idx] + py[i] + sy[i]);    printf("%lld\n", ans >> 1);    return 0;}