跳蚤国王的游戏

Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个n行m列的网格上排兵布阵。其中的c个格子中(0<=2c<=nm-3), 每个格子有一只跳蚤,另有c个格子,每个格子中有一只蛐蛐,剩下的nm-2c个格子 是空的。
我们定义跳蚤国王获胜,当某个时刻,网格中存在连续的k个格子,每个格子中 都是跳蚤。连续的k个格子是指,选定某个格子,选定某个方向(上,右,上左,上 右),从这个格子开始在这个方向上连续的k个格子。同理我们可以定义蛐蛐国王获 胜。
在一开始的网格上,保证不存在一方己经获胜,保证至少有3个空格子。
接下来跳蚤国王和蛐蛐国王轮流行动,跳蚤国王先手。跳蚤国王行动的时候,可 以在网格的任意一个空格子里放一只跳蚤;蛐蛐国王行动的时候,可以在网格的任意 一个空格子里放一只蛐蛐。如果某时刻某一方己经获胜,则游戏结束。
现在跳蚤国王想知道,网格中有多少个空格子,使得跳蚤国王第一步在该格子中 放一只跳蚤之后,可以在一步之内获胜。
跳蚤国王在一步之内获胜的意思是,跳蚤国王己经获胜,或者,不论蛐蛐国王下 一步如何行动,蛐蛐国王都不能获胜,且跳蚤国王在接下来的一步中都存在一种获胜 的方案。
跳蚤国王当然知道怎么做啦!但是他想考考你。

Input

包含多组测试数据。
输入的第一行只有一个整数T,表示数据的组数。保证1<=T<= 100。
接下来依次输入T组数据,每组数据的第一行包含四个整数n,m,k,c。保证 $ 1 <= n, m <= 10^9, 5 <= k <= 10^5 , 0 <= 2c <= min (nm - 3,2 * 10^5) $。
接下来c行,每行包含两个整数x,y,表示第x行,第y列的格子被一只跳蚤占 据。保证1 <= x <= n,1 <= y <= m;每一组数据当中,同一只跳蚤不会被多次描述。
接下来c行,每行包含两个整数x,y,表示第x行,第y列的格子被一只蛐蛐占 据。保证1 <= x <= n,1 <= y <= m;每一组数据当中,同一只蛐蛐不会被多次描述。
同一行相邻的整数之间由一个空格隔开。
我们记 $\sum $ c为T组输入数据的所有c的总和,保证 $\sum c <= 10^5 $。

Output

对于每一组数据依次输出一行一个整数,表示网格中有多少个格子,使得跳蚤国 王第一步在该格子中放一只跳蚤之后,可以在一步之内获胜。

Sample Input

4 12 12 9 7 3 3 4 4 5 5 6 6 7 7 8 8 9 9 12 1 12 2 12 3 11 1 11 2 11 3 1 12 8 8 5 4 3 3 3 4 3 5 3 7 7 3 7 4 8 3 8 4 8 8 5 4 3 3 3 4 3 5 3 6 7 3 7 4 7 5 7 6 8 8 5 4 3 3 3 4 3 5 1 1 7 3 7 4 7 5 7 6

Sample Output

2 3 2 0

Hint

jiangzijing2015

Source

2016年中国大学生程序设计竞赛(合肥)-重现赛(感谢安徽大学)

提交代码