题目描述

给定一个网格图，其中有一些坏点，要求使起点到终点的路径上的所有点到离该点最近的坏点的最小距离距离最大，求这个最大值。

输入格式

第一行输入包含两个整数：$w_x$ 和 $w_y$，以一个空格分隔，它们分别表示网格的宽度和长度（满足 $2 \le w_x,w_y \le 1000$）。

第二行输入包含四个整数：$p_x$、$p_y$、$k_x$ 和 $k_y$，以空格分隔；其中 $(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$）。

第三行输入包含一个整数 $n$，表示有 $n$ 个坏点的坐标（满足 $1 \le n \le w_x \cdot w_y$）。任意两个坏点不会占据同一个位置，并且它们都不会位于 $(p_x,p_y)$ 或 $(k_x,k_y)$。

输出格式

在标准输出的第一行也是唯一一行中，应输出一个整数，即答案的平方。如果路径无法避免直接经过坏点，则结果为 $0$。

5 5
1 1 5 5
2
3 3
4 2

4