P16527 [THUPC 2026 Final] Treasure Hunt in the Exhibition Area

From the final of the 2026 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2026). Resources such as editorials can be found at https://github.com/dapingguo8/THUPC2026-final. --- > After deciding the location of the main venue, Xiao T and Xiao S began arranging the celebration site. On the only path leading to the main venue, they set up a wide exhibition area to showcase wonderful moments from ten years of THUPC. > > Xiao T planned the exhibition area as a huge grid. The outermost ring and some inner cells were set as exhibition walls. To make it convenient for everyone to visit along the planned route, he carefully designed all exhibition walls to form a 4-connected structure. > > To make the visiting process more interesting, Xiao S decided to hold a treasure hunt here.

Xiao T planned the exhibition area as a $n \times n$ 2D grid. The outermost boundary of the grid is surrounded by a ring of exhibition walls, i.e., all cells whose $x$-coordinate or $y$-coordinate equals $0$ or $n + 1$ are exhibition wall cells. In addition, inside the exhibition area there are $m$ exhibition wall cells scattered around, and the coordinates of the $i \ (1 \le i \le m)$-th one are $(x_i, y_i)$. **It is guaranteed that all exhibition wall cells are 4-connected.** After on-site testing, Xiao T summarized the time cost rules for moving in the grid. Specifically, there are two ways to move between cells: - Move one cell in one of the four directions (up, down, left, right), i.e., from $(x, y)$ to one of the adjacent cells $(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)$, which costs $2$ units of time. - Move one cell diagonally, i.e., from $(x, y)$ to one of the diagonal cells $(x - 1, y - 1), (x - 1, y + 1), (x + 1, y - 1), (x + 1, y + 1)$, which costs $3$ units of time. Of course, the destination cell cannot be an exhibition wall cell. **Note: when moving diagonally, you may pass directly through the gap between two diagonally adjacent exhibition wall cells. For example, even if both $(x, y + 1)$ and $(x + 1, y)$ are exhibition wall cells, you can still spend $3$ units of time to move directly from $(x, y)$ to $(x + 1, y + 1)$ diagonally.** Xiao S placed a total of $q$ treasures in the exhibition area. For the $i \ (1 \le i \le q)$-th treasure, she will announce its location $(tx_i, ty_i)$, and at the time of the announcement your position is $(sx_i, sy_i)$. To grab each treasure as fast as possible, you need to compute the minimum time cost to move from your position to the treasure's position.

The first line contains three positive integers $n, m, q \ (1 \le n \le 10 ^ 5, \ 1 \le m, q \le 3 \times 10 ^ 5)$. The next $m$ lines describe the exhibition wall cells. The $i \ (1 \le i \le m)$-th line contains two positive integers $x_i, y_i \ (1 \le x_i, y_i \le n)$, indicating the coordinates of the $i$-th exhibition wall cell. The next $q$ lines describe the treasures. The $i \ (1 \le i \le q)$-th line contains four positive integers $sx_i, sy_i, tx_i, ty_i \ (1 \le sx_i, sy_i, tx_i, ty_i \le n)$, indicating your position and the treasure's position when the $i$-th treasure is announced. It is guaranteed that all exhibition wall cell coordinates are pairwise distinct, and all positions $(sx_i,sy_i),(tx_i,ty_i)$ are not exhibition wall cells.

Output $q$ lines, each containing one integer as the answer. In particular, if you cannot move to the treasure's position, output $-1$.

For the second treasure, you can move along the following path: $(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$, with a total time cost of $2 + 3 + 3 + 3 + 2 + 3 = 16$. Translated by ChatGPT 5