P2711. 构成正方形的数量

解题思路

暴力解思路

一个正方形由4个顶点构成，暴力解的思路非常直接。 以4个点为一组，枚举所有这样的组，然后判断这些组是否可以构成正方形并且统计数量即可。

考虑这种思路的计算量，当N取最大值100时，一共需要枚举 C(100,4) 组。 用时间复杂度来考虑，这种做法四重for循环，复杂度为 O(N^4)，因此这样的暴力解思路必然在某些用例下超时。

故本篇题解对暴力解的做法略去不表。

根据对角线构建单个正方形

现在我们从考虑4个点降低到仅考虑2个点的情况。假设我们已知两个点 P1 和 P2 的坐标，分别记其坐标为 (x1, y1) 和 (x2, y2)。

注意这两个点的选择是任意的，连接这两个点，我们可以做出如下的图：

如果以这条线段作为某正方形的对角线，我们可以得到 P3 和 P4 两个点，他们之间的连线线段 P3P4 是正方形的另一条对角线，和对角线 P1P2 互相垂直且长度相等。

当我们已知 P1 和 P2 的坐标 (x1, y1) 和 (x2, y2) 时，我们可以通过计算来算出正方形的另外两个点 P3 和 P4 的坐标 (x3, y3) 和 (x4, y4)。

经过四个点，做出x轴或y轴的平行线，可以得到一个4条边平行于x轴和y轴的正方形以及4个全等三角形。设这4个全等三角形的两条直角边的长度分别为 a 和 b，即有：

结合 P1 和 P2 的坐标，我们可以得到如下图的数量关系：

容易列出方程组：

其中 a 和 b 是未知数，x1, x2, y1, y2 是已知量。容易解得：

解出 a 和 b 之后，我们容易通过观察得到 P3 和 P4 的坐标：

• P3 的坐标为 (x1 + b, y1 + a)
• P4 的坐标为 (x1 + a, y1 - b)

写成代码即为：

哈希集合判断是否存在正方形

在计算得到 P3 和 P4 的坐标之后，剩下的内容就显而易见了。 我们仅需要判断题目所给的所有的点的集合，P3、P4 是否存在于这个集合中即可。

很容易想到，为了进行快速搜索，我们可以将原先的所有点储存在一个哈希集合 points_set 中：

可以构建出如下的 check() 函数：

我们可以枚举所有的 P1 和 P2，然后判断其对应的 P3 和 P4 是否存在，这样就仅用双重for循环来完成搜索的过程，将时间复杂度降到 O(N^2)，这样就可以在 N 最大值取 100 的条件下通过本题了。

注意，最终的答案 ans 必须整除 2 后再输出。 这是因为，在当前的遍历方式中，我们会在考虑 P1P2 构成的对角线时寻找对应的 P3 和 P4 点，也会在考虑以 P3P4 为对角线时找到 P1 和 P2 点。 换句话说，每一个可以构成的正方形，会被重复计算1次。 因此最终的答案必须整除 2。