← 返回题目列表

AtCoder · abc133_b

B. 良好的距离

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

分数: 200 点

问题陈述

有 N 点 D维空间。

的坐标 i第一点是 (X_{i1}, X_{i2}, ..., X_{iD}).

有坐标的两点之间的距离 (y_1, y_2, ..., y_D) 和 (z_1, z_2, ..., z_D) is \sqrt{(y_1 - z_1)^2 + (y_2 - z_2)^2 + ... + (y_D - z_D)^2}.

多少对 (i, j) (i < j) 之间的距离是否存在 i第点和 j第一点是整数?

约束

  • 输入中的所有值都是整数。 您选择的
  • 2 \leq N \leq 10
  • 1 \leq D \leq 10
  • -20 \leq X_{ij} \leq 20
  • 没有两个给定点具有相同的坐标。也就是说,如果 i \neq j,存在 k 这样 X_{ik} \neq X_{jk}.

输入

输入由标准输入按以下格式给出:

N D
X_{11} X_{12} ... X_{1D}
X_{21} X_{22} ... X_{2D}
\vdots
X_{N1} X_{N2} ... X_{ND}

输出

打印对数 (i, j) (i < j) 使得之间的距离 i第点和 j第一个点是一个整数。


示例输入 1

3 2
1 2
5 5
-2 8

示例输出 1

1

整数距离的对的数量为 1,如下:

  • 第一个点和第二个点之间的距离是 \sqrt{|1-5|^2 + |2-5|^2} = 5,这是一个整数。
  • 第二点和第三点之间的距离是 \sqrt{|5-(-2)|^2 + |5-8|^2} = \sqrt{58},它不是整数。
  • 第三点和第一点之间的距离是 \sqrt{|-2-1|^2+|8-2|^2} = 3\sqrt{5},它不是整数。

示例输入 2

3 4
-3 7 8 2
-12 1 10 2
-2 8 9 3

示例输出 2

2

示例输入 3

5 1
1
2
3
4
5

示例输出 3

10