← 返回题目列表

AtCoder · icpc2013spring_f

F. 点距离

中文机器翻译题面 查看原题

问题陈述

您在发明中心担任兼职程序员。该中心研究蛋白质分子的运动。它需要分子如何形成簇,因此它将计算所有分子对的距离并绘制直方图。 分子的位置由下式给出 N x N 网格地图。 价值 细胞的 C_{xy} 网格地图中的 (x, y) 意味着 C_{xy} 分子位于以下位置 (x, y).

给你一张网格图,请计算所有分子对的直方图。


输入

输入格式如下。

N
C_{11} C_{12} ... C_{1N}
C_{21} C_{22} ... C_{2N}
...
C_{N1} C_{N2} ... C_{NN}

第一行包含网格地图大小 N (1 \leq N \leq 1024)。 每一个下一个 N 行包含 N 数字。 每个号码 C_{xy} (0 \leq C_{xy} \leq 9) 是指位置(x,y)的分子数。 至少有2个分子。

输出

输出格式如下。

D_{ave}
d_{1} c_{1}
d_{2} c_{2}
...
d_{m} c_{m}

打印 D_{ave} 第一行所有分子对的平均距离。 接下来,打印所有对距离的直方图。 每行包含一个距离 d_i 和分子对的数量 c_i(0 \lt c_i)。 距离 d_i 应通过欧氏距离平方计算并按升序排序。 如果不同距离的数量超过10,000,请显示前10,000行。 答案可以用任意数量的十进制数字打印,但不得包含大于或等于的绝对或相对误差 10^{-8}.

示例输入 1

2
1 0
0 1

样本输入 1 的输出

1.4142135624
2 1

示例输入 2

3
1 1 1
1 1 1
1 1 1

样本输入 2 的输出

1.6349751825
1 12
2 8
4 6
5 8
8 2

示例输入 3

5
0 1 2 3 4
5 6 7 8 9
1 2 3 2 1
0 0 0 0 0
0 0 0 0 1

样本输入 3 的输出

1.8589994382
0 125
1 379
2 232
4 186
5 200
8 27
9 111
10 98
13 21
16 50
17 37
18 6
20 7
25 6