시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 768 MB 6 6 6 100.000%

문제

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

예제 입력 1

5
-3 2
0 0
0 5
1 2
4 3

예제 출력 1

19

예제 입력 2

3
0 2
4 0
0 0

예제 출력 2

5

In Day 0 :

100000
000000
300020

In Day 1 :

110000
100020
330222

In Day 2 :

111020
110222
332222

$f(1, 2)=2$, $f(1, 3) = 1$, $f(2, 3) = 2$. Thus the answer is $5$

출처