Problem 2. Equilateral Triangles

USACO 2020 February Contest, Platinum

Farmer John 的牧场可以被表示为一个 $N\times N$ 的正方形方阵（$1\le N\le 300$），包含 $1\le i,j\le N$ 内的所有位置 $(i,j)$。对于方阵内的每个方格，如果在这个位置上有一头奶牛，输入中对应的字符为 '*'，如果这个位置没有奶牛则为 '.'。

FJ 相信他的牧场的美丽程度正比于两两距离相等的奶牛三元组的数量。也就是说，她们组成一个等边三角形。不幸的是，直到最近 FJ 才发现，由于他的奶牛都处在整数坐标位置，如果使用欧几里得距离进行计算，不可能存在美丽的奶牛三元组！于是，FJ 决定改用“曼哈顿”距离。形式化地说，两点 $(x_0,y_0)$ 和 $(x_1,y_1)$ 之间的曼哈顿距离等于 $|x_0-x_1|+|y_0-y_1|$。

给定表示奶牛位置的方阵，计算等边三角形的数量。

测试点性质： 除了样例之外有十四个测试点，依次满足 $N\in \{50,75,100,125,150,175,200,225,250,275,300,300,300,300\}$。

输入格式（文件名：triangles.in）：

第一行包含一个整数 $N$。

对于每个 $1\le i\le N$，第 $i+1$ 行包含一个长为 $N$ 的仅由字符 '*' 和 '.' 组成的字符串。第 $j$ 个字符描述了是否在位置 $(i,j)$ 存在一头奶牛。

输出格式（文件名：triangles.out）：

输出一个整数，为所求的答案。可以证明答案可以用 32 位有符号整数型存储。

输入样例：

3
*..
.*.
*..

输出样例：

1

有三头奶牛，并且她们组成了一个等边三角形，因为每对奶牛之间的曼哈顿距离都等于二。

供题：Benjamin Qi