시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 776 | 95 | 52 | 13.333% |
N×M크기의 직사각형이 있고, 1×1크기의 단위 정사각형으로 나누어져 있다. 각각의 정사각형 중심에는 점이 한 개 찍혀있고, 색은 빨강, 초록, 파랑중의 하나다.
서로 다른 세 개의 점을 선택해보자. 선택한 세 점은 일직선 상에 있어도 된다. 그리고 세 점을 서로 연결한다. 그럼 삼각형을 만들 수 있다. (일직선도 삼각형이다) 만약 이런 삼각형의 꼭짓점 색이 서로 다르다면 이 삼각형을 아름다운 삼각형이라고 한다.
만약 아름다운 삼각형 A와 아름다운 삼각형 B가 두 개의 꼭짓점이 같고, B의 넓이가 A보다 크다면, 삼각형 A를 커질 수 있는 아름다운 삼각형이라고 한다. (일직선 모양의 삼각형 넓이는 0이다)
N×M 직사각형이 주어질 때, 서로 다른 커질 수 있는 아름다운 삼각형의 개수를 출력하는 프로그램을 작성하시오.
첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 내부 모양이 주어진다. R은 빨강, G는 초록, B는 파랑이다. N과 M은 50보다 작거나 같은 자연수이다.
첫째 줄에 커질 수 있는 아름다운 삼각형의 개수를 출력하면 된다.
3 8 RRRRRRRR GGGGBBBB RRRRRRRR
240
1 3 RGB
0
2 3 RGB RGB
6
8 8 RBRBRBRB BRBRBRBR RBRBRBRB BRBRBRBR RRRRRRRR BBBBBBBB RRRRBBBB BBBBRRRR
0
6 3 RGB RBG GRB GBR BRG BGR
208