레이팅 미적용농부 존의 목초지는 모든 \(1\le i,j\le N\)에 대한 위치 \((i,j)\)로 이루어진 \(N\times N\) 정사각 격자\((1\le N\le 300)\)로 나타낼 수 있다. 격자의 각 칸에 대해, 입력에서 그에 대응하는 문자는 그 위치에 소가 한 마리 있으면 '*', 소가 없으면 '.'이다.
농부 존은 목초지의 아름다움이, 위치들이 서로 같은 거리에 있는 소 세 마리의 조합, 즉 정삼각형을 이루는 소 삼중쌍의 개수에 정비례한다고 믿는다. 안타깝게도 농부 존은 아주 최근에야, 모든 소가 정수 좌표에 있으므로 유클리드 거리를 사용하면 아름다운 삼중쌍이 존재할 수 없다는 것을 깨달았다! 그래서 농부 존은 대신 "맨해튼" 거리를 사용하기로 했다. 형식적으로, 두 위치 \((x_0,y_0)\)와 \((x_1,y_1)\) 사이의 맨해튼 거리는 \(|x_0-x_1|+|y_0-y_1|\)이다.
소들의 위치를 나타내는 격자가 주어질 때, 정삼각형 삼중쌍의 개수를 계산하시오.
문제 제공: Benjamin Qi
배점
예제 외에 열네 개의 테스트 케이스가 있으며, \(N\in \{50,75,100,125,150,175,200,225,250,275,300,300,300,300\}\)의 각 값에 대해 하나씩이다.
문제 제공: Benjamin Qi
첫째 줄에 정수 \(N\)이 하나 주어진다.
각 \(1\le i\le N\)에 대해, 입력의 \(i+1\)번째 줄에 문자 '*'와 '.'만으로 이루어진 길이 \(N\)의 문자열이 주어진다. \(j\)번째 문자는 위치 \((i,j)\)에 소가 있는지 없는지를 나타낸다.
답을 나타내는 정수 하나를 출력한다. 답은 부호 있는 32비트 정수 범위에 들어감을 보일 수 있다.
triangles.in · 출력을 쓸 파일 triangles.out3
*..
.*.
*..1There are three cows, and they form an equilateral triple because the Manhattan
distance between each pair of cows is equal to two.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > February > Platinum