[AdditionalFile5497.zip](file://AdditionalFile5497.zip?type=additional_file)

#5497. 「POI2006 R1」青蛙 Frogs

标签: 传统 | 时间限制: 3000 ms | 内存限制: 64 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – I etap Żaby

字节国（Bajtocja）爆发了一场蛙灾，它们正在摧毁所有的庄稼。农夫 Bajtazar 决定使用特殊的驱赶器来对抗这些青蛙，他将这些驱赶器布置在田地的选定位置。每只青蛙在从一个地方移动到另一个地方时，都会尽量与驱赶器保持尽可能远的距离，也就是说，它会最大化其与最近驱赶器的距离。

Bajtazar 的田地呈矩形。青蛙在田地上沿着与田地边缘平行的方向跳跃，每次跳跃的距离为一个单位长度。对于一条路径而言，其与驱赶器的距离被定义为：青蛙在该路径上所有位置中，离各个驱赶器距离的最小值。

Bajtazar 知道青蛙最常从哪里跳到哪里，并且正在尝试不同的驱赶器布局。他请求你的帮助，希望你能编写一个程序，对于给定的驱赶器布局，计算出青蛙在田地上从一个地点移动到另一个地点的过程中，能够保证的与驱赶器之间的最大安全距离。

请编写一个程序，实现以下功能：

• 从标准输入读取田地的大小、驱赶器的位置以及青蛙的起始和终点位置，
• 计算出青蛙在其路径上能够保证的、与最近驱赶器之间的最大距离，
• 将所找到距离的平方输出到标准输出。

输入格式

输入的第一行包含两个整数 $w_x, w_y$ $(2 \le w_x, w_y \le 1000)$，由单个空格隔开，表示田地的宽度和长度。

输入的第二行包含四个整数 $p_x, p_y, k_x, k_y$ $(1 \le p_x, k_x \le w_x, 1 \le p_y, k_y \le w_y)$，由单个空格隔开；($p_x, p_y$) 是青蛙的起始位置，($k_x, k_y$) 是青蛙的终点位置。

输入的第三行包含一个整数 $n$ $(1 \le n \le w_x \cdot w_y)$，表示布置在田地上的驱赶器数量。

接下来的 $n$ 行包含各个驱赶器的坐标。对于 $1 \le i \le n$，第 $i+3$ 行包含两个整数 $x_i$ 和 $y_i$ $(1 \le x_i \le w_x, 1 \le y_i \le w_y)$，由单个空格隔开，表示第 $i$ 个驱赶器的坐标。每个驱赶器都位于不同的位置，且没有任何驱赶器位于起点 $(p_x, p_y)$ 或终点 $(k_x, k_y)$。

输出格式

输出的第一行且仅一行应包含一个整数，即青蛙必须接近的最近驱赶器的最大可能距离的平方。如果青蛙无法避免直接跳到某个驱赶器上，输出 $0$。

样例

输入

5 5
1 1 5 5
2
3 3
4 2

输出

4

青蛙的最优路径如下：