Ray Tracing

题意翻译

在一个$n\times m$的矩形房间里有$k$个传感器,第$i$个传感器位于$(x_i,y_i)$,所有的传感器位置互不相同 房间的一对对角位于$(0,0)$和$(n,m)$,房间的墙壁与坐标轴平行 在时刻$0$,有一束光线从$(0,0)$出发,向$(1,1)$的方向释放,这束光线以$\sqrt{2}m/s$的速度传播,因此,光线将在出发后恰好$1s$时到达点$(1,1)$ 当光线碰到墙壁时,它将遵循反射角等于入射角的规则进行反射,当它碰到$4$个角中的任意一个时,就会立刻停止 对于每一个传感器,你需要计算光线第一次到达这个传感器所在点的时刻,如果光纤永远不会经过这个传感器,那么输出$-1$ ###### 输入格式 输入的第一行包括$3$个整数$n,m,k$($2\leq n,m\leq 10^5$,$1\leq k\leq 10^5$)——房间墙壁的长度和传感器的数量 接下来的$k$行,每一行包括两个整数$x_i$和$y_i$($1\leq x_i\leq n-1$,$1\leq y_i\leq m-1$)——传感器的坐标,保证没有任何两个传感器有坐标相同 ###### 输出格式 输出共$k$行,第$i$行应该输出光线第一次经过第$i$个传感器所在点的时刻;或是当光线永远不会穿过这个传感器所在的点时,输出$-1$ ###### 说明 在第一组样例中,光线将依次通过点$(0,0)\ (1,1)\ (2,2)\ (3,3)$。他将在$3s$后在$(3,3)$停下 第二组样例,光纤将会依次穿过如下的点:$(0,0)\ (1,1)\ (2,2)\ (3,3)\ (2,4)\ (1,3)\ (0,2)\ (1,1)\ (2,0)\ (3,1)\ (2,2)\ (1,3)\ (0,4)$。光线将在$12s$后在$(0,4)$停下,分别在点$(3,3)\ (2,4)\ (0,2)\ (2,0)\ (3,1)$处进行一次反射

题目描述

There are $ k $ sensors located in the rectangular room of size $ n×m $ meters. The $ i $ -th sensor is located at point $ (x_{i},y_{i}) $ . All sensors are located at distinct points strictly inside the rectangle. Opposite corners of the room are located at points $ (0,0) $ and $ (n,m) $ . Walls of the room are parallel to coordinate axes. At the moment $ 0 $ , from the point $ (0,0) $ the laser ray is released in the direction of point $ (1,1) $ . The ray travels with a speed of ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF724C/2826342a15affce70e459206e8466cd2b66552a3.png) meters per second. Thus, the ray will reach the point $ (1,1) $ in exactly one second after the start. When the ray meets the wall it's reflected by the rule that the angle of incidence is equal to the angle of reflection. If the ray reaches any of the four corners, it immediately stops. For each sensor you have to determine the first moment of time when the ray will pass through the point where this sensor is located. If the ray will never pass through this point, print $ -1 $ for such sensors.

输入输出格式

输入格式


The first line of the input contains three integers $ n $ , $ m $ and $ k $ ( $ 2<=n,m<=100000 $ , $ 1<=k<=100000 $ ) — lengths of the room's walls and the number of sensors. Each of the following $ k $ lines contains two integers $ x_{i} $ and $ y_{i} $ ( $ 1<=x_{i}<=n-1 $ , $ 1<=y_{i}<=m-1 $ ) — coordinates of the sensors. It's guaranteed that no two sensors are located at the same point.

输出格式


Print $ k $ integers. The $ i $ -th of them should be equal to the number of seconds when the ray first passes through the point where the $ i $ -th sensor is located, or $ -1 $ if this will never happen.

输入输出样例

输入样例 #1

3 3 4
1 1
1 2
2 1
2 2

输出样例 #1

1
-1
-1
2

输入样例 #2

3 4 6
1 1
2 1
1 2
2 2
1 3
2 3

输出样例 #2

1
-1
-1
2
5
-1

输入样例 #3

7 4 5
1 3
2 2
5 1
5 3
4 3

输出样例 #3

13
2
9
5
-1

说明

In the first sample, the ray will consequently pass through the points $ (0,0) $ , $ (1,1) $ , $ (2,2) $ , $ (3,3) $ . Thus, it will stop at the point $ (3,3) $ after $ 3 $ seconds. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF724C/7ada4f061afa5fde77b267e1fa49961f4954e4b1.png)In the second sample, the ray will consequently pass through the following points: $ (0,0) $ , $ (1,1) $ , $ (2,2) $ , $ (3,3) $ , $ (2,4) $ , $ (1,3) $ , $ (0,2) $ , $ (1,1) $ , $ (2,0) $ , $ (3,1) $ , $ (2,2) $ , $ (1,3) $ , $ (0,4) $ . The ray will stop at the point $ (0,4) $ after $ 12 $ seconds. It will reflect at the points $ (3,3) $ , $ (2,4) $ , $ (0,2) $ , $ (2,0) $ and $ (3,1) $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF724C/a784221a8237fedf4ebaf6ee9bba924202f51f94.png)