P4800. 亲近度排名矩阵

场次：2026年4月18日-开发岗 · 来源：CodeFun2000 P4800

题目描述

在一项地理数据分析中，收集了 $n$ 个地点的坐标，每个地点 $i$ 对应两个整数坐标 $(x_i, y_i)$。

对任意两个不同的地点 $i$ 和 $j$，定义它们的亲近度为

$$d(i,j) = (x_i - x_j)^2 + (y_i - y_j)^2$$

亲近度越小表示两点越接近。

对于每个地点 $i$，考虑所有 $j \ne i$ 并按亲近度从小到大排序。如果另有 $k \ne i,j$ 满足 $d(i,k) \le d(i,j)$，则称 $k$ 是 $i$ 到 $j$ 的一个“近邻”。记 $S(i,j)$ 为这些近邻的个数。形式化定义：

• 若 $i \ne j$，$S(i,j) = \#\{ k \mid k \ne i, k \ne j, d(i,k) \le d(i,j) \}$；
• $S(i,i) = 0$。

你的任务是：对于给定的 $n$ 个地点，计算出 $n \times n$ 的矩阵 $S$。

约束条件：

• 测试数据组数 $T$ 不超过 $100$；
• 每组数据的地点数 $n \ge 1$，且所有组的 $n$ 之和不超过 $2000$；
• 所有坐标均为不超过 $10^9$ 的正整数。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。
对于每组数据：

• 第一行包含一个整数 $n$，表示地点的个数；
• 接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$，表示第 $i$ 个地点的坐标。

保证所有测试数据中 $n$ 的总和不超过 $2000$。

输出格式

对于每组数据，输出 $n$ 行，每行包含 $n$ 个整数，表示矩阵 $S$ 的对应行。第 $i$ 行的第 $j$ 个整数表示 $S(i,j)$。同一行内的整数以单个空格分隔。各组测试数据的输出之间不需要额外的空行。

示例

示例 1

输入：

1
1
10 20

输出：

0

说明：

只有 1 个地点，根据定义 $S(1,1)=0$，因此直接输出 0。

示例 2

输入：

1
3
1 1
2 2
3 3

输出：

0 0 1
1 0 1
1 0 0

说明：

共有 3 个地点，坐标分别为 $(1,1), (2,2), (3,3)$。

对地点 1（$(1,1)$）：

• 与地点 2 的距离平方 $d(1,2)=2$，没有其他点满足 $\le 2$，故 $S(1,2)=0$。
• 与地点 3 的距离平方 $d(1,3)=8$，地点 2 满足 $d(1,2)=2 \le 8$，故 $S(1,3)=1$。

对地点 2（$(2,2)$）：

• 与地点 1 的距离平方 $d(2,1)=2$，与地点 3 的距离平方 $d(2,3)=2$，两者距离相同。排序后该组最后一个位置为 1，故 $S(2,1)=S(2,3)=1$。

对地点 3（$(3,3)$）：

• 与地点 2 的距离平方 $d(3,2)=2$，无其他点满足 $\le 2$，故 $S(3,2)=0$。
• 与地点 1 的距离平方 $d(3,1)=8$，地点 2 满足 $d(3,2)=2 \le 8$，故 $S(3,1)=1$。

对角线恒为 0。

示例 3

输入：

1
3
0 0
0 1
1 0

输出：

0 1 1
0 0 1
0 1 0

说明：

三个地点构成等腰直角三角形。

对地点 1 $(0,0)$：到地点 2 的距离平方为 1，到地点 3 的距离平方也为 1，两者相同，排序后组内最后一个位置为 1，因此 $S(1,2)=S(1,3)=1$。

对地点 2 $(0,1)$：到地点 1 的距离平方为 1（位置 0），到地点 3 的距离平方为 2（位置 1），故 $S(2,1)=0$，$S(2,3)=1$。

对称地，地点 3 $(1,0)$ 的结果为 $S(3,1)=1$，$S(3,2)=0$。

所有对角线元素均为 0。