OI Problems   关于

#jhfvu6. 理想城

时间限制:1 s       空间限制:250 MiB       标签: 动态规划 树形动态规划 IOI 2012 

算法难度等级:4       思维难度等级:5       实现难度等级:5


本题来源于:IOI 2012

  • 简体中文
  • 形式化题意

题目描述

像许多同龄的科学家和艺术家一样,小 L 对城市规划和城区设计很感兴趣.他致力于构建一个理想城。理想城由 NN 个区块组成,而这些区块放在一个无限大的正方形网格上。第 xx 行第 yy 列的单元格由有序数对 (x,y)(x,y)来标识。单元格 (0,0)(0,0) 位于网格的左上角。给定一个单元格 (x,y)(x,y),与之相邻的单元格(如果存在的话)分别为:(x1,y)(x-1,y)(x+1,y)(x+1,y)(x,y1)(x,y-1)(x,y+1)(x,y+1)。每个区块在网格上恰好覆盖一个单元格。一个区块能够被放置在单元格 (x,y)(x,y) 上,当且仅当 1x,y23121 \le x,y \le 2^{31}-2 。我们将使用单元格的坐标同时来代表单元格上面的区块。若两个区块被放在相邻的单元格中,则视它们为相邻区块.理想城所有的区块连在一起,里面没有“洞”存在.换言之,所有单元格必须满足下述两个条件:

  • 对于任意两个空白的单元格,至少存在一连串相邻的空白单元格连接它们。
  • 对于任意两个非空的单元格,至少存在一连串相邻的非空单元格连接它们。

以下 44 个图中的区块放置均不满足理想城的条件。前两个图不满足第一个条件。第 33 个图不满足第二个条件,第 44 个图两个条件均不满足。

当遍历理想城时,一个跳步代表从一个区块走到一个相邻的区块。跳步时不能移进空白单元格。假设 v0,v1,,vN1v_0,v_1,\cdots,v_{N-1}NN 个区块的坐标。对于任意两个不同的区块 viv_ivjv_j,它们的距离 d(vi,vj)d(v_i,v_j) 是从 viv_i 移动到 vjv_j 所需的最小跳步数目。

下图是一个由 1111 个区块组成的理想城。区块坐标分别为

v0=(2,5)v1=(2,6)v2=(3,3)v_0=(2,5) \quad v_1=(2,6) \quad v_2=(3,3)

v3=(3,6)v4=(4,3)v5=(4,4)v_3=(3,6) \quad v_4=(4,3) \quad v_5=(4,4)

v6=(4,5)v7=(4,6)v8=(5,3)v_6=(4,5) \quad v_7=(4,6) \quad v_8=(5,3)

v9=(5,4)v10=(5,6)v_9=(5,4) \quad v_{10}=(5,6)

其中,d(v1,v3)=1d(v_1,v_3)=1d(v1,v8)=6d(v_1,v_8)=6d(v6,v10)=2d(v_6,v_10)=2d(v9,v10)=4d(v_9,v_10)=4

给定一个理想域,试求

S=i=0N2j=i+1N1d(vi,vj)S=\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1}d(v_i,v_j)

输入格式

11 行为一个正整数 NN,为理想城区块的数目。

22 行到第 N+1N+1 行,每行有两个非负整数。第 i+2i+2 行为第 ii 个区块的坐标 v_i = (x_i, y_i)。

输出格式

输出仅一行一个正整数,为 SS 的值。由于 SS 的值可能较大,你只需输出 SS10910^9 取模的值。

输入输出样例

11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
174

提示

对于 100%100\% 的数据,1N1051 \le N \le 10^51xi,yi23121 \le x_i,y_i \le 2^{31}-2

有一个网格图,其中有 NN 个格子被染成黑色,其余为白色。被染色的第 ii 个格子处于第 xix_i 行,yiy_i 列,保证这个网格图是合法的,即黑格和白格是分别四联通的,就是说对于任意两个同色格子,可以通过与其同色的格子组成的路径到达。

求两两黑格最段路之和。