#P1783. 海滩防御

海滩防御

题目描述

WLP 同学最近迷上了一款网络联机对战游戏(终于知道为毛 JOHNKRAM 每天刷洛谷效率那么低了),但是他却为了这个游戏很苦恼,因为他在海边的造船厂和仓库总是被敌方派人偷袭。于是,WLP 动用了他那丰满且充实的大脑(或许更偏向前者),想出了一个好主意,他把海滩分成垂直于海岸线的若干列,在其中的几列上放置几个信号塔,试图来监视整个海滩。然而,WLP 是一个非常心急的人,他把信号塔建好后才发现还需给信号塔供能,它们才能投入使用(这不是废话么),它们都有一个工作半径,一个圆形区域里的所有敌人都逃不过它们的监视,不过,WLP 发现,敌人们非常狡猾,除非他将道路完全封死,否则 WLP 的敌人可以走过一条任意弯曲的路(不一定走整点,但是不会出第 00 列和第 NN 列构成的边界)来偷他的东西。

于是,WLP 就思考了:到底需要给每个信号塔多大的工作半径,才能将从海滩到内地的路径完全封死呢?他再次动用了他那丰满且充实的大脑,想了一堂数学课,终于,还是没想出来。于是,他向 LZZ 神犇求助(额…… CSUNSHINE 的身份是不是暴露了)。

终于,在 WLP:“ %^!*@#!*(*^!*#@$^&(此处省略无数卖萌场景)”的哀求下,LZZ 神犇写了一个程序,在一秒内就解决了问题。但是,邪恶的 LZZ 神犇决定要将这个难题共享给无数无辜的 OIer,所以,现在轮到你了。

输入格式

第一行两个整数 NNMM,表示海滩被 WLP 分成的列数 0,1,2,,N0,1,2,\cdots,N 和信号塔个数。

22 至第 M+1M+1 行,每行两个数 XiX_iYiY_i 表示 1,2,3,,M1,2,3,\cdots,M 号信号塔所在的列数和离开海滩的距离。

输出格式

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

5 5
1 5
3 5
5 5
4 30
2 15
1.00
100 2
30 50
90 100
39.05

提示

数据范围及约定

  • 对于 10%10\% 的数据:1M101 \le M \le 101Yi1001 \le Y_i \le 100
  • 对于 30%30\% 的数据:1M501 \le M \le 501Yi1,0001 \le Y_i \le 1,000
  • 对于 80%80\% 的数据:1M5001 \le M \le 5001Yi1,0001 \le Y_i \le 1,000
  • 对于 100%100\% 的数据:1M8001 \le M \le 8001N10001 \le N \le 10001XiN1 \le X_i \le N1Yi100,0001 \le Y_i \le 100,000

提示

注意,封锁海滩是指,敌人的深入程度是有限制的,若敌人绕过了所有的信号塔,并且可以长驱直入,那么就说明道路没有完全封锁。