#P9716. 碰壁
碰壁
题目描述
平面上有一个 行 列的矩形网格,左下角坐标为 ,右上角坐标为 。 与 互质,且 为奇数。
一个大小可忽略的小球从 出发,初速度为 ,即向左上方运动。某些格子各放有一个方块,方块占据整个格子。小球碰到网格外边界或方块边界时发生镜面反射。每次小球撞到方块后,被撞到的方块立即消失。
已知所有方块的位置,求从小球出发到所有方块消失所需的时间。
输入格式
第一行三个整数 ,依次表示列数、行数和方块数。
接下来 行,每行两个整数 ,表示一个方块的右上角坐标为 。保证 。
输出格式
输出一行一个整数,表示所有方块消失的时间。
样例
5 4 3
1 1
1 2
1 4
42
数据范围
- 对于 20% 的数据,。
- 对于 70% 的数据,。
- 对于全部数据,,,所有输入均为整数。原题共 10 个测试点,每个占 10%。
原题时间限制 1 秒,内存限制 512 MB。