该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Good Distance

题目描述

在 $D$ 维空间中有 $N$ 个点。 第 $i$ 个点的坐标为 $(X_{i1}, X_{i2}, ..., X_{iD})$。 坐标为 $(y_1, y_2, ..., y_D)$ 和 $(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$ 个点之间的距离是整数？

输入格式

标准输入的给定格式如下： $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) 的数量。

3 2

1 2

5 5

-2 8

1

3 4

-3 7 8 2

-12 1 10 2

-2 8 9 3

2

5 1

1

2

3

4

5

10

提示

输入中的所有值均为整数。 $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}$。整数距离的对的数量为一，如下：

第一个点与第二个点之间的距离为 $\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}$，这不是整数。

标签: AtCoder|abc133B

来源

AtCoder|abc133B