记录编号	603443	评测结果	AAAAAAAAAAAAAAA
题目名称	3369.[USACO20 Feb Platinum]Equilateral Triangles	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	1.302 s
提交时间	2025-07-12 14:47:10	内存使用	21.03 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll N=1010;
char s;
ll n,a[N][N],b[N][N],f[N][N],ans,cnt;
struct node{
	ll x,y;
}p[N*N];

int main(){
	freopen("usaco_Feb_Triangles!.in","r",stdin);
	freopen("usaco_Feb_Triangles!.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>s;
			if(s=='*') a[i][j]=1;
		}
	}
	for(int i=1;i<=4;i++){
		cnt=0;
		memset(b,0,sizeof(b));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				b[i][j]=a[i][j];
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				a[j][i]=b[n-i+1][j];
			}
		}
		for(int i=1;i<=n*2;i++){
			for(int j=1;j<=n*2;j++){
				f[i][j]=f[i-1][j+1]+a[i][j];
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(a[i][j]==1){
					p[++cnt].x=i;
					p[cnt].y=j;
				}
			}
		}
		for(int i=1;i<=cnt;i++){
			for(int k=1;k<=n;k++){
				ll xa=p[i].x,ya=p[i].y;
				ll xb=p[i].x-k,yb=p[i].y+k;
				if(xb<1||yb>n) break;
				if(a[xb][yb]==0) continue;
				ans+=f[xa+k][ya+k]-f[xa][ya+k*2];
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}