|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||64 MB||3||1||1||33.333%|
The area of the Great Bytean Mountains can be imagined as a rectangle in a plane with cartesian coordinate system. This rectangle has two opposite vertices in points (0,0) and (w,h), where w and h are positive integers. There are n major peaks in the mountains, each of which is located in one grid point of the rectangle (a grid point is a point having integer coordinates). More and more tourists discover the beauty of Great Bytean Mountains and everyone would like to build a house there. The rules of Great Bytean Mountain Park are very strict though: in each grid point of the rectangle at most one house can be built and moreover there cannot be any house on the peak of any mountain. So there are (w + 1)·(h + 1) − n possible locations of houses.
Some of the locations are considered better than other. We say that a grid point (x, y) has a northern neighbour if there is a mountain peak in some point (x, y + d), where d is a positive integer. Similarly, southern, eastern and western neighbours could be defined. In this way, every grid point that is not a mountain peak may have between 0 and 4 neighbours — the more neighbours, the better is the location (because of a better view of the mountains). The director of Great Bytean Mountain Park would like to know the maximal profit that can be achieved by selling locations to tourists. Help him and count how many grid points in the mountains (excluding mountain peaks) have 0, 1, 2, 3 and 4 neighbours.
Write a program which:
The first line of input contains three integers w, h and n (1 ≤ w,h ≤ 109 , 1 ≤ n ≤ 500000), separated by single spaces. The following n lines contain the descriptions of locations of mountain peaks in the park. Each of them contains two integers x and y (0 ≤ x ≤ w, 0 ≤ y ≤ h), separated by a single space. All peaks are in distinct locations.
The first and only line of output should contain 5 integers, separated by single spaces and denoting the numbers of grid points (excluding peaks), having exactly 0, 1, 2, 3 and 4 neighbours.
4 3 6 0 3 2 3 2 1 0 1 3 2 1 2
1 7 2 3 1
Points having two neighbours are: (3,1) and (3,3), points with three neighbours are: (1,1), (0,2) and (1,3). Point (2,2) has four neighbours, point (4,0) does not have any neighbours and all remaining points have exactly one neighbour each.