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

P3438 [POI 2006] ZAB-Frogs

题目描述

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

输入格式

第一行输入包含两个整数：$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$。

输入输出样例 #1

输入 #1

5 5
1 1 5 5
2
3 3
4 2

输出 #1

4

#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

青蛙的最优路径如下：