시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)178806444.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 $이 추가된다. 

입력으로 들어오는 직선은 모두 다르다.

출력

큰 정삼각형 안에 있는 정삼각형의 개수를 출력한다. 일부만 큰 정삼각형 안에 있는 정삼각형은 포함하지 않으며, 점은 정삼각형이 아니다. 큰 정삼각형도 자기 자신 안에 있다.

예제 입력 1

2 3
0 1
60 1
120 1

예제 출력 1

5

예제 입력 2

10 5
60 1
120 2
0 1
120 5
60 9

예제 출력 2

12

노트

두 예제의 삼각격자와 직선을 그려보면 다음과 같다.

그림 F.2: 예제 1에 해당하는 그림 그림 F.3: 예제 2에 해당하는 그림

출처

University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2021 예선 F번