The Sprawl

Kim is playing a city-building simulation game on an infinite chessboard. Every cell is denoted by two integers $(x, y)$. Two cells are adjacent if they share an edge. Formally, cell $(x, y)$ is adjacent to four cells, $\{(x+1, y), (x, y+1), (x-1, y), (x, y-1)\}$.

In the beginning (day 0), city $i$ occupies the single cell $(x_i, y_i)$. If a cell is occupied by any city, it is called a developed cell. Thus, on day 0, there are exactly $N$ developed cells.

After each day, each city grows and expands by occupying any undeveloped adjacent cells. Formally, for each city $i$, let $S_i$ be the set of cells adjacent to at least one cell of city $i$. Starting from city 1 to city $n$, any undeveloped cell in $S_i$ becomes part of city $i$ and becomes developed.

Two cities $u, v$ are "connected" when you can move from $(x_u, y_u)$ to $(x_v, y_v)$ passing only between adjacent developed cells. For two cities $u, v$, let $f(u, v)$ be the first day on which cities $u, v$ become connected. Kim is interested in each value of $f(u, v)$, but there are too many values to consider. Thus, for the given starting cells, Kim only wants to calculate $\sum_{1 \leq i < j \leq N}{f(u, v)}$.

The first line contains the number of cities $N$.

The next $N$ lines give the starting cell of the $i$-th city as two integers $x_i, y_i$.

Print $\sum_{1 \leq u < v \leq N}{f(u, v)}$, where $f(u, v)$ is the first day on which cities $u, v$ become connected.

• $1 \leq N \leq 250000$
• $-10^7 \leq x_i, y_i \leq 10^7$
• All given cells are distinct