#3293. 「BalticOI 2012 Day1」移动网络

内存限制:64 MiB 时间限制:600 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: StudyingFather

题目描述

译自 BalticOI 2012 Day1 T2. Mobile

著名移动网络运营商 Totalphone 新修了一些网络基站,来覆盖即将通车的高速公路。

由于 Totalphone 的工程师很懒,所有基站的发射功率都是一样的。为了最大限度地降低功耗,该公司想知道高速公路上的点到最近基站的距离最大值是多少。

输入格式

输入第一行两个整数 N,L ,分别代表基站的数目和高速公路的长度。高速公路是一条从 (0,0) (L,0) 的线段。

接下来 N 行,第 i 行两个整数 (x_i,y_i) ,描述了第 i 个基站的坐标,保证没有两个基站在同一个点上。

输入的基站按照 x 坐标递增的顺序排序,当 x 坐标相同的时候,按 y 坐标递增的顺序排序。

输出格式

输出一个实数,即高速公路上的点到最近基站的距离最大值。

你的输出与标准输出的误差不超过 10^{-3} 即被认为正确。

样例

样例输入

2 10
0 0
11 1

样例输出

5.545455

数据范围与提示

  • 对于 25\% 的数据: N \leq 5 \times 10^3
  • 对于 50\% 的数据: N \leq 10^5
  • 对于 100\% 的数据: 1 \leq N \leq 10^6 1 \leq L \leq 10^9 -10^9 \leq x_i,y_i \leq 10^9