[APIO2012]苦无

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 kunai.in 输出文件 kunai.out
【问题描述】 
苦无(Kunai)是一种忍者使用的形状像刀的武器,忍者通过投掷苦无攻击对
手。 
现在有N名忍者聚集在一块H行W列的棋盘式的广场上。每个忍者都站在
其所在方块的中心处,任何两个忍者都不在同一个方块上。每个忍者都拿着一个
苦无,面朝上、下、左、右四个方向中的一个方向站着。在时刻0,所有忍者同
时向其所朝向的方向投掷苦无。 
每个苦无将会一直保持其初始的方向,并以单位速度飞行。如果某个时刻一
个位置上多于一个的苦无,它们将会相撞并且消失。苦无特别小,可以看成质点。
同时,由于忍者的移动速度特别快,他们不会被苦无击中。 
在下面的例子中,我们用箭头来表示苦无,而箭头的方向即为苦无的方向。
在这些图中,所有的苦无都会相撞后消失。 
 
在下面的图中,两个粗线箭头表示的苦无不会相撞。其中在第二个和第三个
图中,其中一个粗线表示的苦无会与细线表示的苦无相撞后消失,因此不会撞上
另一个粗线表示的苦无。 
 
你的任务是计算经过足够长的时间之后,在这个W × H的广场中有多少格
子被苦无经过。 
【数据范围】 
1 ≤ N ≤ 100,000  忍者数; 
1 ≤ W ≤ 1,000,000,000  列数; 
1 ≤ H ≤ 1,000,000,000  行数; 
1 ≤ Xi ≤ W,1 ≤ Yi ≤ H  坐标范围。 
 
在10%的数据中,N ≤ 1000, W ≤ 1000, H ≤ 1000。 

在40%的数据中,N ≤ 1000。

【输入格式】 
从标准输入读入数据。 
第一行包含两个被空格隔开的整数W, H,表示广场的尺寸为W列H行。 
第二行包含一个整数N,表示忍者的数量。 
接下来N行中,第i行有三个以空格分隔的整数Xi, Yi, Di
, 表示第i个忍者
处在从左往右的Xi 列、从上往下的第Yi 行,任何两个忍者不在同一个位置。第
i个忍者面向的方向由Di 表示,分别为: 
  Di = 0,表示忍者向右; 
  Di = 1,表示忍者向上; 
  Di = 2,表示忍者向左; 
  Di = 3,表示忍者向下。 
【输出格式】 
输出到标准输出。 
输出一个整数,表示经过足够长的时间之后,在这个W × H的广场中被苦
无经过被苦无经过的格子数量。 
【样例输入1】 
5 4 

3 3 2 
3 2 0 
4 2 2 
5 4 1 
1 1 3 
【样例输出1】 
11 
【样例说明】 
在时刻0,苦无的情况如下图所示 
 
在下面的描述中,忍者i投掷的苦无将用苦无i表示。 
在时刻0.5,苦无2和苦无3相撞后消失。 
下图为时刻1的情况,加深的格子表示已经被苦无经过。

在时刻2,苦无1和苦无5相撞后消失,此时的广场如下图所示。 
 
之后没有苦无相撞。再经过足够时间后的广场如下图所示。 
 
共有11个格子被苦无经过,因此输出11。 
【样例输入2】 
7 6 
12 
3 2 3 
6 3 2 
7 1 3 
1 5 0 
3 6 1 
6 6 1 
4 5 2 
1 3 0 
6 5 2 
5 1 2 
6 4 3 
4 1 3 
【样例输出2】 
29