分数: 500 点
问题陈述
有一个网格 H 行和 W 列。牢房位于 r从顶部算起的第行和 c从左边算起的第列称为单元格 (r,c)。每个单元格被漆成黑色或白色:单元格 (R_k,C_k) 为黑色 k=1,2,\ldots,N,剩余的 HW-N 细胞为白色。
找到该网格中矩形区域的数量 h 行和 w 列,其中包含的所有单元格都涂成白色。
更正式地说,找到整数对的数量 (r_0, c_0) 满足以下所有条件:
- 1\le r_0 \le H-h+1
- 1\le c_0 \le W-w+1
- 细胞 所有整数对的 (r_0+i,c_0+j) 被涂成白色 (i,j) 满意 0\le i< h,\ 0\le j< w.
约束
- 1\le h\le H\le 10^9
- 1\le w\le W\le 10^9
- 0\le N\le 2\times 10^5
- 1\le R_k\le H
- 1\le C_k\le W
- (R_{k_1},C_{k_1}) \neq (R_{k_2},C_{k_2}) (k_1 \neq k_2)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
H W h w N R_1 C_1 R_2 C_2 \vdots R_N C_N
输出
输出答案。
示例输入 1
3 4 2 2 3 1 3 2 4 3 1
示例输出 1
2
下图中红色包围的两个矩形区域满足所有条件。

示例输入 2
4 4 3 2 2 2 2 3 4
示例输出 2
0
没有矩形区域满足所有条件。
示例输入 3
449 449 3 14 0
示例输出 3
194892
示例输入 4
31 9 5 7 10 14 8 8 4 18 8 12 1 8 5 9 6 18 1 14 7 5 6 26 7
示例输出 4
12