#B. Good Distance

    传统题 2000ms 1024MiB

Good Distance

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

问题陈述

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 点之间的距离是整数?

限制因素

  • 所有输入值均为整数。
  • 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}

输入

输入内容由标准输入法提供,格式如下:

  • 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 点之间的距离为整数。

3 2
1 2
5 5
-2 8
1

距离为整数的配对数为 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} ,不是整数。
3 4
-3 7 8 2
-12 1 10 2
-2 8 9 3
2
5 1
1
2
3
4
5
10

ABC133 A~E

未参加
状态
已结束
规则
ACM/ICPC
题目
5
开始于
2024-10-18 14:00
结束于
2024-10-18 15:40
持续时间
1.7 小时
主持人
参赛人数
10