#P1514. [POI2006]ZAB-Frogs
[POI2006]ZAB-Frogs
题目描述
给定一个矩形网格,其中有一些坏点。你要从起点到达终点,每次只能向上、下、左、右移动一格,且不能离开网格。
格点 到坏点 的距离是欧几里得距离 。一个格点的安全距离是它到最近坏点的距离;一条路径的安全距离是路径上所有访问格点(包括起点和终点)的安全距离的最小值。
只考察访问的格点,不考察相邻格点之间线段内部的位置。允许路径经过坏点,但这种路径的安全距离为 。
求所有起点到终点路径中,安全距离最大值的平方。
输入格式
第一行输入包含两个整数: 和 ,以一个空格分隔,它们分别表示网格的宽度和长度(满足 )。
第二行输入包含四个整数:、、 和 ,以空格分隔;其中 是路径的起点, 是路径的终点(满足 ,)。
第三行输入包含一个整数 ,表示有 个坏点的坐标(满足 )。任意两个坏点不会占据同一个位置,并且它们都不会位于 或 。
接下来 行,每行包含两个整数 ,表示一个坏点的坐标,满足 、。
输出格式
输出一行一个整数,表示所有路径中最大安全距离的平方。如果路径无法避免直接经过坏点,则输出 。
输入输出样例 #1
输入 #1
5 5
1 1 5 5
2
3 3
4 2
输出 #1
4