15929번 - The Sprawl 다국어

Kim is playing a city-building simulation game in an infinite chessboard. Every cell is denoted with two integer $(x, y)$. Two cells are adjacent if they share an edge - formally, cell $(x, y)$ is adjacent with 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, then it’s called  *developed cells*. Thus, in day 0, there is exactly $N$ developed cells.

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

We call two city $u, v$ “connected”, when you can move between $(x_u, y_u)$ to $(x_v, y_v)$ by only passing between adjacent developed cells. For two city $u, v$, let $f(u, v)$ the first day where two city $u, v$ become connected. Kim is interested in each values of $f(u, v)$, but there are too much values to consider. Thus, Kim only want to calculate $\sum_{1 \leq i < j \leq N}{f(u, v)}$ for a given first developed cells.

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

In next $N$ lines, the position of $i$-th city’s starting cell is given as two integer $x_i, y_i$.

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

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