#ABC133B. Good Distance

Good Distance

题目描述

There are NN points in a DD-dimensional space.

The coordinates of the ii-th point are (Xi1,Xi2,...,XiD)(X_{i1}, X_{i2}, ..., X_{iD}).

The distance between two points with coordinates (y1,y2,...,yD)(y_1, y_2, ..., y_D) and (z1,z2,...,zD)(z_1, z_2, ..., z_D) is $\sqrt{(y_1 - z_1)^2 + (y_2 - z_2)^2 + ... + (y_D - z_D)^2}$.

How many pairs (i,j)(i, j) (i<j)(i \lt j) are there such that the distance between the ii-th point and the jj-th point is an integer?

在一个 DD 维空间中有 NN 个点。

ii 个点的坐标是 (Xi1,Xi2,...,XiD)(X_{i1}, X_{i2}, ..., X_{iD})

坐标为 (y1,y2,...,yD)(y_1, y_2, ..., y_D)(z1,z2,...,zD)(z_1, z_2, ..., z_D) 的两点之间的距离为 $\sqrt{(y_1 - z_1)^2 + (y_2 - z_2)^2 + ... + (y_D - z_D)^2}$ 。

(i,j)(i, j)(i<j)(i \lt j) 有多少对? (i<j)(i \lt j) ,使得第 ii 个点与第 jj 个点之间的距离是整数?

输入格式

输入内容按以下格式标准输入:

NN DD
X11X_{11} X12X_{12} ...... X1DX_{1D}
X21X_{21} X22X_{22} ...... X2DX_{2D}
\vdots
XN1X_{N1} XN2X_{N2} ...... XNDX_{ND}

输出格式

打印 (i,j)(i, j) (i<j)(i \lt j)ii (第 1 个点)与 jj (第 1 个点)之间的距离为整数的线对数。 (i<j)(i \lt j) ,使得第 ii 个点与第 jj 个点之间的距离为整数。

样例 #1

样例输入 #1

3 2
1 2
5 5
-2 8

样例输出 #1

1

样例 #2

样例输入 #2

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

样例输出 #2

2

样例 #3

样例输入 #3

5 1
1
2
3
4
5

样例输出 #3

10

说明

数据规模与约定

  • 所有输入值均为整数。
  • 2N102 \leq N \leq 10
  • 1D101 \leq D \leq 10
  • 20Xij20-20 \leq X_{ij} \leq 20
  • 没有两个给定点的坐标是相同的。也就是说,如果 iji \neq j ,则存在 kk 这样的 XikXjkX_{ik} \neq X_{jk}

样例 11 解释

距离为整数的配对数为 1,如下所示:

  • 第一点与第二点的距离为 152+252=5\sqrt{|1-5|^2 + |2-5|^2} = 5 ,是整数。
  • 第二点与第三点的距离为 5(2)2+582=58\sqrt{|5-(-2)|^2 + |5-8|^2} = \sqrt{58} ,不是整数。
  • 第三点与第一点之间的距离为 212+822=35\sqrt{|-2-1|^2+|8-2|^2} = 3\sqrt{5} ,不是整数。