시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 178 | 80 | 64 | 44.138% |
삼각형은 의외로 위대하다. 원은 만 3세면 따라그릴 수 있으며, 사각형은 만 4세면 그릴 수 있다. 그러나 삼각형은 그보다 1년은 더 지나야 그릴 수 있다고 알려져 있다 (안효섭, 신희영, 『홍창의 소아과학』, 미래앤(2020), 12판). 이하는 만 5살이 된지 한참 되었기 때문에, 무리 없이 종이에 펜으로 변의 길이가 $m$인 '큰 정삼각형'을 하나 그렸다.
이하의 호기심을 조금 더 알아보기 전에 삼각격자에 대한 정의가 필요하다. 좌표평면에서 $ x $축이 $ y $축과 직각을 이루는 직각좌표계와는 달리, 삼각격자는 다음 그림과 같이 $ x $축과 $ y $축이 이루는 각도가 60도이다. 여기에 $x + y = m$ 꼴의 직선을 그으면 다음 그림과 같이 $ (0,0) $, $ (m,0) $, $ (0,m) $을 꼭짓점으로 갖는 정삼각형이 하나 만들어진다. 이 정삼각형을 '큰 정삼각형'이라고 하자.
그림 F.1: 삼각격자의 양 축과 $x+y=m$ 꼴 직선
이하는 더더욱 많은 정삼각형을 그리고 싶어서, 세 변 중 하나에 평행하면서 큰 정삼각형의 내부를 지나가는 직선을 $q$개 그은 다음 큰 정삼각형에 포함되지 않는 부분은 지워 버렸다. 그러자 정삼각형이 꽃처럼 피어났다!
이하는 수많은 정삼각형을 보며 행복해졌으나, 이내 그림에 정삼각형이 총 몇 개나 있는지 궁금해졌다. 손으로 세기에는 너무 많아 보이니, 이하의 질문에 답할 수 있는 프로그램을 작성해 보자.
첫째 줄에는 큰 정삼각형의 한 변의 길이를 나타내는 정수 $ m $과 이하가 새로 그은 직선의 개수 $ q $가 공백으로 구분되어 주어진다. ($ 1 \leq m \leq 200\ 000 $, $ 0 \leq q \leq 3m-3$) 큰 정삼각형의 꼭짓점은 삼각격자에서 $ (0,0) $, $ (m,0) $, $ (0,m) $이다.
그 다음 $ q $개의 줄에는 각각 두 개의 정수 $ d $와 $ l $이 공백으로 구분되어 주어진다. ($ 0 < l < m $) $ d $는 $ x $축과 이루는 각도를 의미하며 $0$, $60$, $120$ 중 하나이다. $ d $가 $ 0 $이면 직선 $ y=l $이, $ 60 $이면 직선 $ x=l $이, $ 120 $이면 직선 $ x+y=l $이 추가된다.
입력으로 들어오는 직선은 모두 다르다.
큰 정삼각형 안에 있는 정삼각형의 개수를 출력한다. 일부만 큰 정삼각형 안에 있는 정삼각형은 포함하지 않으며, 점은 정삼각형이 아니다. 큰 정삼각형도 자기 자신 안에 있다.
2 3 0 1 60 1 120 1
5
10 5 60 1 120 2 0 1 120 5 60 9
12
두 예제의 삼각격자와 직선을 그려보면 다음과 같다.
그림 F.2: 예제 1에 해당하는 그림 | 그림 F.3: 예제 2에 해당하는 그림 |
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2021 예선 F번