← 返回比赛
已结束 【提高组】GESP“飞翔杯”第二届季度赛
← 上一题 下一题 →

A4785 | 迷宫

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

一觉醒来，你梦游到了神秘迷宫。

神秘迷宫是一个 $n\times m$ 的方形区域，其中左下角为 $(0,0)$ ，右上角为 $(n,m)$ 。左边界为入口，右边界为出口。

神秘迷宫中有 $k$ 个引力柱，依次位于 $(x_1,y_1)...(x_k,y_k)$ 。

神秘迷宫的上下边界同样也存在着引力。

你需要从左边界的任意一个点走到右边界的任意一个点，路径是任意的一条所有点都在边界内的连续曲线。

但你不希望受到引力的干扰，也就是你希望路程中离任意引力柱或上下边界的距离的最小值最大，请你求出这个值再进行闯关。

输入格式

一行三个整数 $n,m,k$ 。

接下来 $k$ 行，每行两个整数 $x_i,y_i$ 。

输出格式

输出一个浮点数表示答案，误差不超过 $10^{-6}$ 视为正确。

输入输出样例

输入 #1
10 5 2
1 1
2 3
输出 #1
1.11803399
C++ 编辑器
输入
输出