CF491B New York Hotel

将纽约视为一个由 $N$ 条垂直大道（编号为 $1$ 到 $N$）和 $M$ 条水平街道（编号为 $1$ 到 $M$）组成的矩形网格。有 $C$ 个朋友分别住在 $C$ 家酒店中，这些酒店位于某些街道与大道的交叉点上。他们打算在其中一家 $H$ 家餐厅（同样位于某些交点）为其中一位朋友庆祝生日。他们希望，使得所有人前往餐厅途中，单人所需行走的最大距离尽可能地小。请帮助朋友们选择一个最佳的餐厅举办聚会。 假设相邻两个交叉点之间的距离均为 $1$ 千米。

第一行包含两个整数 $N$ 和 $M$——城市的规模（$1 \leq N, M \leq 10^{9}$）。 第二行包含一个整数 $C$（$1 \leq C \leq 10^5$）——朋友所住酒店的数量。 接下来的 $C$ 行，每行包括两个整数 $x$ 和 $y$（$1 \leq x \leq N$，$1 \leq y \leq M$），表示一家酒店的坐标。 接下来的第一行包含一个整数 $H$（$1 \leq H \leq 10^5$）——餐厅数量。 接下来的 $H$ 行，每行包括两个整数 $x$ 和 $y$（$1 \leq x \leq N$，$1 \leq y \leq M$），表示一个餐厅的坐标。 多家餐厅或酒店可能位于同一个交叉点上。

输出两行。 第一行输出最优距离。 第二行输出实现该最优距离的餐厅索引。如果有多个方案，可以输出其中任意一种。

由 ChatGPT 5 翻译