#P1514. [POI2006]ZAB-Frogs

    ID: 526 传统题 1000ms 512MiB 尝试: 306 已通过: 80 难度: 7 上传者: 标签>CF2300提高+/省选-平方欧氏距离变换单调栈向下取整与向上取整二分答案广度优先搜索

[POI2006]ZAB-Frogs

题目描述

给定一个矩形网格,其中有一些坏点。你要从起点到达终点,每次只能向上、下、左、右移动一格,且不能离开网格。

格点 (x,y)(x,y) 到坏点 (a,b)(a,b) 的距离是欧几里得距离 (x−a)2+(y−b)2\sqrt{(x-a)^2+(y-b)^2}。一个格点的安全距离是它到最近坏点的距离;一条路径的安全距离是路径上所有访问格点(包括起点和终点)的安全距离的最小值。

只考察访问的格点,不考察相邻格点之间线段内部的位置。允许路径经过坏点,但这种路径的安全距离为 00。

求所有起点到终点路径中,安全距离最大值的平方。

输入格式

第一行输入包含两个整数:wxw_x 和 wyw_y,以一个空格分隔,它们分别表示网格的宽度和长度(满足 2≤wx,wy≤10002 \le w_x,w_y \le 1000)。

第二行输入包含四个整数:pxp_x、pyp_y、kxk_x 和 kyk_y,以空格分隔;其中 (px,py)(p_x,p_y) 是路径的起点,(kx,ky)(k_x,k_y) 是路径的终点(满足 1≤px,kx≤wx1 \le p_x,k_x \le w_x,1≤py,ky≤wy1 \le p_y,k_y \le w_y)。

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

接下来 nn 行,每行包含两个整数 ai,bia_i,b_i,表示一个坏点的坐标,满足 1≤ai≤wx1\le a_i\le w_x、1≤bi≤wy1\le b_i\le w_y。

输出格式

输出一行一个整数,表示所有路径中最大安全距离的平方。如果路径无法避免直接经过坏点,则输出 00。

输入输出样例 #1

输入 #1

5 5
1 1 5 5
2
3 3
4 2

输出 #1

4