시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB228594122.162%

문제

쿠나이(수리검)은 칼과 비슷하게 생긴 닌자들이 사용하는 정교한 무기이다. 닌자들은 이 칼을 적에게 던져서 적을 공격한다.

H개의 행(row)과 W개의 열(column)의 정사각형으로 이루어진 격자에 N명의 닌자가 있다. 모든 닌자는 정사각형의 중앙에 있으며, 하나의 정사각형에는 단 한 명의 닌자만 있을 수 있다. 각 닌자는 쿠나이를 가지고 있으며 네 방향(위, 아래, 좌 우) 중 한쪽 방향을 바라보고 있다. 초기(시간 0)에, 모든 닌자들은 자신들의 쿠나이를 그가 바라보고 있는 방향으로 던진다.

모든 쿠나이는 직선방향으로 1의 속도로 나아간다. 동시에 하나보다 많은 쿠나이가 같은 장소에 도달하면, 쿠나이들은 서로 충돌하여 사라진다. 쿠나이의 크기는 너무 작아서 무시할 수 있다. 또한, 닌자들은 매우 빨리 움직이기 때문에 쿠나이에 맞지 않는다. 쿠나이는 다른 쿠나이와 부딪히지 않는 한 속도가 줄어들지 않고 계속 같은 방향으로 움직인다.

다음의 그림에서, 화살표는 쿠나이를 나타낸다. 화살표의 방향이 쿠나이가 움직이는 방향이다. 다음의 그림에서 굵게 표시한 쿠나이는 충돌하는 것들이다.

반면에, 다음의 각 그림에서는, 굵게 표시한 화살표는 다른 굵은 화살표와 충돌하지 않는다. 두 번째와 세 번째 그림에서 얇은 화살표는 다른 굵은 화살표와 충돌한다. 충돌한 화살표는 사라지기 때문에, 이 그림들에서는 굵은 화살표가 다른 굵은 화살표와 충돌하지 않는다.

W*H 격자에서 충분한 시간이 지난 후 쿠나이가 지나간 정사각형의 수를 계산하라.

입력

첫 줄에는 격자의 크기를 나타내는 두 정수 W와 H가 하나의 빈칸을 사이에 두고 주어진다. (1 ≤ W ≤ 1 000 000 000, 1 ≤ H ≤ 1 000 000 000)

두 번째 줄에는 닌자의 수를 나타내는 하나의 정수 N이 주어진다. (1 ≤ N ≤ 100 000)

그 다음 N개의 줄 중에서 i-번째 줄은 왼쪽으로부터 Xi-번째 열(column)과 위로부터 Yi-번째 행(row)에 있는 닌자 i의 위치를 나타내는 세 정수 Xi,Yi,Di가 주어진다. 같은 위치에는 두 명의 닌자가 있을 수 없다. 닌자 i의 방향은 Di의 값으로 나타낸다. (1 ≤ Xi ≤ W, 1 ≤ Yi ≤ H)

  • Di = 0이면, 닌자 i는 오른쪽을 향하여 보고 있다.
  • Di = 1이면, 닌자 i는 위쪽을 향하여 보고 있다.
  • Di = 2이면, 닌자 i는 왼쪽을 향하여 보고 있다.
  • Di = 3이면, 닌자 i는 아래쪽을 향하여 보고 있다.

출력

W*H 격자에서 충분한 시간이 지난 후 쿠나이가 지나간 정사각형의 수를 출력한다.

예제 입력 1

5 4
5
3 3 2
3 2 0
4 2 2
5 4 1
1 1 3

예제 출력 1

11

힌트

이 예제에서, 초기의 (시간 0) 격자는 다음과 같이 나타난다. 

닌자 i가 던진 쿠나이를 쿠나이 i라 하자. 시간 0.5에서는 쿠나이 2와 쿠나이 3이 충돌하여 사라질 것이다. 다음의 그림은 시간 1에서의 격자를 보여준다. 회색으로 표시된 정사각형은 쿠나이가 이미 지나간 정사각형을 나타낸다.

시간 2에서는 쿠나이 1과 쿠나이 5가 서로 충돌하여 사라질 것이다. 시간 2인 경우의 격자는 다음의 그림과 같다.

시간 2 이후에는 더 이상 쿠나이가 충돌하지 않는다. 충분한 시간이 지난 후의 격자는 다음과 같다.

마지막으로, 격자에서 쿠나이가 지나각 정사각형의 수는 11이다. 그러므로, 11을 출력해야 한다.

출처

Olympiad > Asia-Pacific Informatics Olympiad > APIO 2012 3번