#P3288. Neighbours

Neighbours

【题意】

w×hw \times h 的矩形有 (w+1)(h+1)(w + 1) * (h + 1) 个整点。有 nn 个黑点,其余为白点。 统计每个白点东南西北四个方向能看到多少个黑点。一个方向最多只能看到一个黑点,后面的黑点被第一个看到的黑点挡住了。 输出能看到黑点个数为0, 1, 2, 3, 4的各类白点的总数。

【输入格式】

输入文件第一行为3个正整数 w,h,n(n5×105,w,h109)w, h, n(n \le 5 \times 10^5, w, h \le 10^9). 以下 nn 行,每行有两个整数 (xi,yi)(xi, yi) , 表示一个黑点的坐标 (0xiw0yih)(0 \le xi \le w , 0 \le yi \le h)

【输出格式】

输出文件有5个数, 分别为能看到黑点个数为0, 1, 2, 3, 4的白点的个数。

【样例输入】

4 3 6
0 3
2 3
2 1
0 1
3 2
1 2

【样例输出】

1 7 2 3 1

【样例解释】

共有(4 + 1) * (3 + 1) – 6 = 14个点 (4, 0)没看到黑点 (3, 1), (3, 3)能看到2个黑点 (0, 2), (1, 1), (1, 3)能看到3个黑点, (2, 2)能看到4个黑点, 其余点均为1个黑点。