30143 - 海滩防御

0N 列的海滩上有 M 个信号塔,第 i 个信号塔位于 (X_i, Y_i)。每个信号塔有一个相同的圆形工作半径 r,可以覆盖半径为 r 的圆形区域。

敌人可以从海滩底部(y 较小处)向内地(y 较大处)前进,可以走任意曲线,但不能越过第 0 列和第 N 列。

你需要确定最小的 r,使得信号塔的覆盖区域能够形成一道从左边界到右边界的连续屏障,阻止敌人从海滩进入内地。

输入

第一行两个整数 NM,分别表示海滩的列数范围和信号塔个数。

接下来 M 行,每行两个整数 X_i, Y_i,表示第 i 个信号塔的坐标。

输出

一行一个实数,表示最小的工作半径 r,保留两位小数。

样例

输入

5 5
1 5
3 5
5 5
4 30
2 15

输出

1.00

输入

100 2
30 50
90 100

输出

39.05

提示

  • 1 \le M \le 800
  • 1 \le N \le 1000
  • 0 \le X_i \le N
  • 0 \le Y_i \le 100000
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题