网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[APIO2012]苦无
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23: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。
苦无(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
5
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