C. Ray Tracing

Codeforces

IDCF724C

Time2000ms

Memory256MB

Difficulty—

greedyhashingimplementationmathnumber theorysortings

English · Original

Chinese · Translation

Formal · Original

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 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. ## Input The first line of the input contains three integers _n_, _m_ and _k_ (2 ≤ _n_, _m_ ≤ 100 000, 1 ≤ _k_ ≤ 100 000) — 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. ## Output 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. [samples] ## Note 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. <center>![image](https://espresso.codeforces.com/c9062b2691bfcc243bd935c3d42e3aaf4b984148.png)</center>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). <center>![image](https://espresso.codeforces.com/f7b736704b4c47b73a05359265c3173d5d58824c.png)</center>

在一间大小为 #cf_span[n × m] 米的矩形房间中有 #cf_span[k] 个传感器。第 #cf_span[i] 个传感器位于点 #cf_span[(xi, yi)]。所有传感器均位于矩形内部的互不相同的点上。房间的对角顶点位于点 #cf_span[(0, 0)] 和 #cf_span[(n, m)]，房间的墙壁与坐标轴平行。在时刻 #cf_span[0]，从点 #cf_span[(0, 0)] 发出一束激光，方向指向点 #cf_span[(1, 1)]。激光以每秒 1 米的速度传播，因此恰好在 1 秒后到达点 #cf_span[(1, 1)]。当激光碰到墙壁时，遵循入射角等于反射角的规律反射。若激光到达四个角中的任意一个，则立即停止。对于每个传感器，你需要确定激光首次经过该传感器所在位置的时刻。如果激光永远不会经过该点，则对此传感器输出 #cf_span[ - 1]。输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[2 ≤ n, m ≤ 100 000], #cf_span[1 ≤ k ≤ 100 000]），分别表示房间墙壁的长度和传感器的数量。接下来的 #cf_span[k] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi ≤ n - 1], #cf_span[1 ≤ yi ≤ m - 1]），表示传感器的坐标。保证没有两个传感器位于同一点。请输出 #cf_span[k] 个整数。第 #cf_span[i] 个整数应为激光首次经过第 #cf_span[i] 个传感器所在位置的秒数，若永远不会经过则输出 #cf_span[ - 1]。在第一个样例中，激光依次经过点 #cf_span[(0, 0)], #cf_span[(1, 1)], #cf_span[(2, 2)], #cf_span[(3, 3)]，因此在 #cf_span[3] 秒后停止于点 #cf_span[(3, 3)]。在第二个样例中，激光依次经过以下点：#cf_span[(0, 0)], #cf_span[(1, 1)], #cf_span[(2, 2)], #cf_span[(3, 3)], #cf_span[(2, 4)], #cf_span[(1, 3)], #cf_span[(0, 2)], #cf_span[(1, 1)], #cf_span[(2, 0)], #cf_span[(3, 1)], #cf_span[(2, 2)], #cf_span[(1, 3)], #cf_span[(0, 4)]。激光在 #cf_span[12] 秒后停止于点 #cf_span[(0, 4)]，并在点 #cf_span[(3, 3)], #cf_span[(2, 4)], #cf_span[(0, 2)], #cf_span[(2, 0)] 和 #cf_span[(3, 1)] 处发生反射。 ## Input 输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[2 ≤ n, m ≤ 100 000], #cf_span[1 ≤ k ≤ 100 000]），分别表示房间墙壁的长度和传感器的数量。接下来的 #cf_span[k] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi ≤ n - 1], #cf_span[1 ≤ yi ≤ m - 1]），表示传感器的坐标。保证没有两个传感器位于同一点。 ## Output 请输出 #cf_span[k] 个整数。第 #cf_span[i] 个整数应为激光首次经过第 #cf_span[i] 个传感器所在位置的秒数，若永远不会经过则输出 #cf_span[ - 1]。 [samples] ## Note 在第一个样例中，激光依次经过点 #cf_span[(0, 0)], #cf_span[(1, 1)], #cf_span[(2, 2)], #cf_span[(3, 3)]，因此在 #cf_span[3] 秒后停止于点 #cf_span[(3, 3)]。在第二个样例中，激光依次经过以下点：#cf_span[(0, 0)], #cf_span[(1, 1)], #cf_span[(2, 2)], #cf_span[(3, 3)], #cf_span[(2, 4)], #cf_span[(1, 3)], #cf_span[(0, 2)], #cf_span[(1, 1)], #cf_span[(2, 0)], #cf_span[(3, 1)], #cf_span[(2, 2)], #cf_span[(1, 3)], #cf_span[(0, 4)]。激光在 #cf_span[12] 秒后停止于点 #cf_span[(0, 4)]，并在点 #cf_span[(3, 3)], #cf_span[(2, 4)], #cf_span[(0, 2)], #cf_span[(2, 0)] 和 #cf_span[(3, 1)] 处发生反射。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the rectangular room, with corners at $ (0,0) $ and $ (n,m) $. Let $ k \in \mathbb{Z}^+ $ be the number of sensors. Let $ S = \{(x_i, y_i) \mid i \in \{1, \dots, k\}\} $ be the set of sensor coordinates, where $ 1 \le x_i \le n-1 $, $ 1 \le y_i \le m-1 $, and all points are distinct. The laser ray starts at $ (0,0) $ at time $ t=0 $, moving with direction vector $ (1,1) $ at speed $ \sqrt{2} $ units per second, so it traverses one unit in both $ x $ and $ y $ per second. The ray reflects off walls obeying the law of reflection (angle of incidence = angle of reflection), and stops upon reaching any corner: $ (0,0) $, $ (n,0) $, $ (0,m) $, or $ (n,m) $. **Constraints** 1. $ 2 \le n, m \le 100{,}000 $ 2. $ 1 \le k \le 100{,}000 $ 3. For all $ i $: $ 1 \le x_i \le n-1 $, $ 1 \le y_i \le m-1 $ 4. All sensor positions are distinct and strictly inside the rectangle. **Objective** For each sensor $ (x_i, y_i) $, compute the smallest $ t \ge 0 $ such that the ray passes through $ (x_i, y_i) $ at time $ t $, or return $ -1 $ if never. Use the method of reflections: unfold the room into a grid of reflected copies. The ray’s path becomes a straight line in this grid with slope 1. The ray passes through $ (x_i, y_i) $ at time $ t $ if and only if there exist integers $ a, b \in \mathbb{Z} $ such that: $$ x_i = |a| \cdot n + (-1)^a \cdot x', \quad y_i = |b| \cdot m + (-1)^b \cdot y' $$ where $ x' \in \{x_i, n - x_i\} $, $ y' \in \{y_i, m - y_i\} $, and the unfolded coordinates satisfy: $$ x_i + a n = y_i + b m = t, \quad \text{with } a + b \text{ even} $$ Equivalently, the ray reaches $ (x_i, y_i) $ at time $ t $ if and only if: $$ t \equiv x_i \pmod{2n}, \quad t \equiv y_i \pmod{2m}, \quad \text{and} \quad t \equiv x_i \equiv y_i \pmod{2} $$ Thus, solve the system: $$ t \equiv x_i \pmod{2n} \\ t \equiv y_i \pmod{2m} \\ t \equiv x_i \pmod{2} $$ and find the minimal non-negative solution $ t $. If no solution exists, return $ -1 $.

Samples

Input #1

Output #1

1
-1
-1
2

Input #2

Output #2

1
-1
-1
2
5
-1

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. Ray Tracing",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF724C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在一间大小为 #cf_span[n × m] 米的矩形房间中有 #cf_span[k] 个传感器。第 #cf_span[i] 个传感器位于点 #cf_span[(xi, yi)]。所有传感器均位于矩形内部的互不相同的点上。\n\n房间的对角顶点位于点 #cf_span[(0, 0)] 和 #cf_span[(n, m)]，房间的墙壁与坐标轴平行。\n\n在时刻 #cf_span[0]，从点 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the dimensions of the rectangular room, with corners at $ (0,0) $ and $ (n,m) $.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of sensors.  \nLet $ S = \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments