| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 768 MB | 102 | 46 | 26 | 63.415% |
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.
5 -3 2 0 0 0 5 1 2 4 3
19
3 0 2 4 0 0 0
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ドル$