曼哈顿距离转成切比雪夫距离,可以发现满足要求的三角形在新的坐标下一定是**一个平行与坐标轴的正方形的两个相邻的顶点和对面的边上的任意一点**连接而成。
那么前缀和计数一下即可,显然要横着和竖着各算一次,时间复杂度 $\mathcal O(n^3)$。
如果出现三个点都是正方形的顶点的情况,会被横着竖着各计算一次,需要去掉这样的情况,在后一次计算的时候不算到即可。
```cpp
const int N = 307;
int n, a[N*2][N*2], b[N*2][N*2];
char s[N];
ll ans;
int main() {
rd(n);
for (int i = 1; i <= n; i++) {
rds(s, n);
for (int j = 1; j <= n; j++)
if (s[j] == '*') a[i+j-1][i-j+n] = 1;
}
n *= 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
b[i][j] = a[i][j] + b[i][j-1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (a[i][j])
for (int k = j + 1; k <= n; k++)
if (a[i][k]) {
if (i - (k - j) >= 1)
ans += b[i-(k-j)][k] - b[i-(k-j)][j-1];
if (i + (k - j) <= n)
ans += b[i+(k-j)][k] - b[i+(k-j)][j-1];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
b[i][j] = a[i][j] + b[i-1][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (a[j][i])
for (int k = j + 1; k <= n; k++)
if (a[k][i]) {
if (i - (k - j) >= 1)
ans += b[k-1][i-(k-j)] - b[j][i-(k-j)];
if (i + (k - j) <= n)
ans += b[k-1][i+(k-j)] - b[j][i+(k-j)];
}
print(ans);
return 0;
}
```