CF2215G Maze

There is an $ (n+2) \times (n+2) $ grid, where both coordinates range from $ 0 $ to $ n+1 $ inclusive. The outermost cells of the grid are all obstacle cells. In addition, there are $ m $ more obstacle cells in the grid. The $ i $ -th obstacle cell is located at $ (x_i, y_i) $ . It is guaranteed that all obstacles (including the outer boundary cells) are 4-connected. That is, you can move between any two obstacle cells by moving up, down, left, or right through other obstacle cells. Little L is walking in this maze. He cannot step into any obstacle cell at any time. If Little L is at position $ (x, y) $ , he can make the following moves: - Move orthogonally to an adjacent cell $ (x+1,y) $ , $ (x-1,y) $ , $ (x,y+1) $ , or $ (x,y-1) $ with a cost of $ 2 $ . - Move diagonally to an adjacent cell $ (x+1,y+1) $ , $ (x+1,y-1) $ , $ (x-1,y+1) $ , or $ (x-1,y-1) $ with a cost of $ 3 $ . There are $ q $ queries. For each query, you are given a starting point and an ending point. You need to find the minimum total cost for Little L to travel from the starting point to the ending point. If it is impossible to reach the ending point, output $ -1 $ .

The first line of the input contains three integers $ n $ , $ m $ , and $ q $ ( $ 1 \le n \le 10^5 $ , $ 1 \le m, q \le 3 \cdot 10^5 $ ). The next $ m $ lines each contain two integers $ x_i $ and $ y_i $ — the coordinates of the $ i $ -th obstacle cell. It is guaranteed that all obstacle coordinates are distinct, and that all obstacles (including the outer boundary cells) are 4-connected. The next $ q $ lines each contain four integers $ s_x $ , $ s_y $ , $ t_x $ , and $ t_y $ — a query with starting point $ (s_x, s_y) $ and ending point $ (t_x, t_y) $ . It is guaranteed that neither $ (s_x,s_y) $ nor $ (t_x,t_y) $ is an obstacle.

For each query, output a single integer — the minimum cost to travel from the starting point to the ending point. Or print $ -1 $ if it is impossible to do so.

For the second query, you can move as follows: $ (1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1) $ . The total cost is $ 2 + 3 + 3 + 3 + 2 + 3 = 16 $ .