题解：AT_abc275_c [ABC275C] Counting Squares

· · 题解

题目传送门

题意让我们在一个（9\times 9）的矩阵里找以四个 # 为四个顶点组成正方形的个数。

思路

可以看到，本题数据范围非常小，最坏情况下，也仅有约 2\times10^6 ，完全可以用暴力枚举。我们可以用 vector 或 set 存一下 # 的位置，然后依次枚举选四个点能不能构成正方形。

重点来了，如何判断四个点能否构成正方形呢？众所周知，构成正方形需要对边相等，且四个角都是直角。

重点就在于判断边。学过初中的都知道，根据勾股定理，三角形的两条直角边的平方和 = 斜边平方。所以我们可以把正方形分成两个一样的三角形，然后按上面去判断。

AC Code

最后，劝大家一句，不要抄袭，AC 记录都没了可不要来找我。