P16527 [THUPC 2026 决赛] 展览区寻宝

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。 题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。 --- > 在确定好主会场的位置后，小 T 和小 S 开始着手布置庆典会场。他们在通往主会场的必经之路上，设置了一块宽阔的展览区，用于展现十年 THUPC 的精彩画面。 > > 小 T 将展览区规划成了一个巨大的网格，最外围以及内部的部分格子被设为展览墙。为了方便大家沿动线参观，他将所有的展览墙精心设计为了四连通的结构。 > > 为了让参观过程更具趣味性，小 S 决定在这里举办一场寻宝活动。

小 T 将展览区规划成一个大小为 $n \times n$ 的二维网格。网格的最外围由一圈展览墙包围，即横坐标或纵坐标等于 $0$ 或 $n + 1$ 的所有格子均为展览墙格子。此外，展览区内部还散布着 $m$ 个展览墙格子，其中第 $i \ (1 \le i \le m)$ 个的坐标为 $(x_i, y_i)$。**保证所有的展览墙格子之间是四连通的。** 经过实地布景测试，小 T 总结出了在网格间移动的耗时规律。具体而言，在格子间有以下两种移动方式： - 沿上下左右方向移动一格，即从 $(x, y)$ 移动到 $(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)$ 中的某一个相邻格子，需要消耗 $2$ 个单位时间。 - 沿对角线方向移动一格，即从 $(x, y)$ 移动到 $(x - 1, y - 1), (x - 1, y + 1), (x + 1, y - 1), (x + 1, y + 1)$ 中的某一个对角格子，需要消耗 $3$ 个单位时间。 当然，移动的目标位置不能是展览墙格子。**注意：沿对角线方向移动时，可以直接从两个对角展览墙格子之间的缝隙穿过。例如，即使 $(x, y + 1)$ 与 $(x + 1, y)$ 均为展览墙格子，依然可以消耗 $3$ 个单位时间，直接从 $(x, y)$ 沿对角线移动到 $(x + 1, y + 1)$。** 小 S 在展览区中总计布置了 $q$ 个宝藏。对于第 $i \ (1 \le i \le q)$ 个宝藏，她会公布它的位置 $(tx_i, ty_i)$，而公布时你所处的位置为 $(sx_i, sy_i)$。为了以最快速度夺得各个宝藏，你需要计算出，从你所处的位置移动到宝藏所在位置的最短耗时。

输入的第一行包含三个正整数 $n, m, q \ (1 \le n \le 10 ^ 5, \ 1 \le m, q \le 3 \times 10 ^ 5)$。 接下来 $m$ 行，第 $i \ (1 \le i \le m)$ 行包含两个正整数 $x_i, y_i \ (1 \le x_i, y_i \le n)$，表示第 $i$ 个展览墙格子的坐标。 接下来 $q$ 行，第 $i \ (1 \le i \le q)$ 行包含四个正整数 $sx_i, sy_i, tx_i, ty_i \ (1 \le sx_i, sy_i, tx_i, ty_i \le n)$，表示公布第 $i$ 个宝藏时你所处的位置与宝藏所在的位置。 保证所有展览墙格子的坐标互不相同，保证所有的 $(sx_i,sy_i),(tx_i,ty_i)$ 位置均不为展览墙格子。

输出 $q$ 行，每行一个整数表示答案。特别地，若你无法移动到宝藏所在的位置，则输出 $-1$。

对于第二个宝藏，你可以沿着以下路径移动：$(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$，总耗时为 $2 + 3 + 3 + 3 + 2 + 3 = 16$。