P6137 [IOI 2012] 理想城

像许多同龄的科学家和艺术家一样，小 L 对城市规划和城区设计很感兴趣.他致力于构建一个理想城。理想城由 $N$ 个区块组成，而这些区块放在一个无限大的正方形网格上。第 $x$ 行第 $y$ 列的单元格由有序数对 $(x,y)$来标识。单元格 $(0,0)$ 位于网格的左上角。给定一个单元格 $(x,y)$，与之相邻的单元格（如果存在的话）分别为：$(x-1,y)$，$(x+1,y)$，$(x,y-1)$，$(x,y+1)$。每个区块在网格上恰好覆盖一个单元格。一个区块能够被放置在单元格 $(x,y)$ 上，当且仅当 $1 \le x,y \le 2^{31}-2$ 。我们将使用单元格的坐标同时来代表单元格上面的区块。若两个区块被放在相邻的单元格中，则视它们为相邻区块.理想城所有的区块连在一起，里面没有“洞”存在.换言之，所有单元格必须满足下述两个条件： - 对于任意两个空白的单元格，至少存在一连串相邻的空白单元格连接它们。 - 对于任意两个非空的单元格，至少存在一连串相邻的非空单元格连接它们。 以下 $4$ 个图中的区块放置均不满足理想城的条件。前两个图不满足第一个条件。第 $3$ 个图不满足第二个条件，第 $4$ 个图两个条件均不满足。  当遍历理想城时，一个**跳步**代表**从一个区块走到一个相邻的区块**。跳步时不能移进空白单元格。假设 $v_0,v_1,\cdots,v_{N-1}$ 是 $N$ 个区块的坐标。对于任意两个不同的区块 $v_i$ 和 $v_j$，它们的距离 $d(v_i,v_j)$ 是从 $v_i$ 移动到 $v_j$ 所需的最小跳步数目。 下图是一个由 $11$ 个区块组成的理想城。区块坐标分别为  $$v_0=(2,5) \quad v_1=(2,6) \quad v_2=(3,3)$$ $$v_3=(3,6) \quad v_4=(4,3) \quad v_5=(4,4)$$ $$v_6=(4,5) \quad v_7=(4,6) \quad v_8=(5,3)$$ $$v_9=(5,4) \quad v_{10}=(5,6)$$ 其中，$d(v_1,v_3)=1$，$d(v_1,v_8)=6$，$d(v_6,v_10)=2$，$d(v_9,v_10)=4$。 给定一个理想域，试求 $$S=\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1}d(v_i,v_j)$$

无

无

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le x_i,y_i \le 2^{31}-2$ 。