Informatica Online Judge

  경곽이의 페인팅 [1770 / 06EA]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 18   Total Tried : 22


The Champion of this Problem (C++) : gs17018 - 5ms / 660byte
My Best Submission (C++) : N/A

[AtCoder]

Background

$H$행 $W$열의 격자 형태로 이루어진 큰 스케치북이 있다.

경곽이는 이 스케치북에 $n$개의 원하는 칸을 검은색으로 칠하려고 한다.

경곽이가 칠하고자 하는 칸은 $a$, $b$로 나타낸다. 이는 $a$행, $b$열을 검은색으로 칠한다는 의미이다.

경곽이가 $n$개의 칸을 모두 칠했다.

이제 경곽이는 다음과 같은 조건을 만족하는 영역이 몇 개씩 있는지 궁금해졌다.

경곽이는 온전한 $3$행 $3$열의 정사각형 영역을 관찰한다.

여기서 온전한 영역이란 도화지 내부에 $3$행 $3$열이 모두 포함되는 것을 말한다.

임의의 $3$행 $3$열 부분은 검은색 점을 $0$개부터 $9$개까지 포함할 수 있다.

경곽이는 도화지 내부의 온전한 모든 $3$행 $3$열의 영역들 중 검은 점을 0개 포함한 영역의 수부터 9개 포함한 영역의 수까지 모두 구하고 싶어졌다.

이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 행의크기와 열의크기를 나타내는 자연수 $H$와 $W$ 및 검은 점의 수 $n$이 공백으로 구분되어 입력된다.

두 번째 줄부터 $n$줄에 걸쳐서 점의 위치를 나타내는 값 $a$, $b$가 한 줄에 하나씩 공백으로 구분되어 입력된다.

[입력값의 정의역]

$3≤H≤10^9$
$3≤W≤10^9$
$0≤n≤min(10^5, H×W)$
$1≤a≤H$
$1≤b≤W$

Output

출력은 다음과 같이 10줄로 출력한다.

첫 번째 줄에는 각 영역이 포함하는 검은 점의 수가 $0$개인 영역의 수
두 번째 줄에는 각 영역이 포함하는 검은 점의 수가 $1$개인 영역의 수
세 번째 줄에는 각 영역이 포함하는 검은 점의 수가 $2$개인 영역의 수
:
열 번재 줄에는 각 영역이 포함하는 검은 점의 수가 $9$개인 영역의 수

IO Example

입력
4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

출력
0
0
0
2
4
0
0
0
0
0


[설명]
위 예시는 그림과 같다.



이 그림에서 각 $3$행 $3$열의 영역들에 대해서 조사하면 출력결과와 같다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]