[POI2006]ZAB-Frogs

时间限制：5s 空间限制：64MB

题目描述

Task: Frogs 一群青蛙正在摧毁Byteotia所有的庄稼. 一个叫Byteasar的农夫决定使用一种放在田里的奇特的"scarefrogs"来吓跑他们, 所有的青蛙在跳跃过程中都尽量使自己离他们越远越好, 即是让自己离最近的scarefrog越远越好. Byteasar的田是块矩形的土地. 青蛙们跳跃的方向平行于坐标轴并且每次跳跃的距离为1. 一条跳跃路线的scarefrogs-距离为路径上所有点距离所有scarefrogs的最近距离. Byteasar已经知道青蛙们的出发位置和目的地位置, 所以他在田里放置了若干个scarefrogs. 他请求你帮忙写一个程序找一条路径使得该路径的scarefrogs-距离最大.

输入格式

第一行包含两个整数: wx 和 wy 分别表示田地的宽和长( 2 <= 1="" wx,="" wy<="1" 000).="" 第二行包含四个整数:="" px,="" py,="" kx="" 和="" ky="" 其中="" (px,="" py)="" 为青蛙的起始位置,="" (kx,="" ky)="" 为目的地位置(="" <="px," 1<="py," ky<="wy)." 第三行一个整数="" n="" –="" 表示scarefrogs的总数(="" wx="" .="" wy).="" 接下来n="" 行描述所有scarefrogs的坐标.="" 坐标用xi="" yi="" 来描述第ith个="" scarefrog的位置="" (="" 没有两个scarefrogs在同一个位置出现并且不会出现在(px,="" nor="" ky)上.="" p="">

输出格式

一个整数代表目标路径scarefrog距离的平方. 如果青蛙不可避免遇到某些scarefrog那么答案为0.

样例输入

样例输出

提示

题目来源

没有写明来源