#P3486. [Baltic2012]mobile

    ID: 2698 传统题 6000ms 64MiB 尝试: 18 已通过: 4 难度: 7 上传者: 标签>难度分类提高+/省选-计算几何直线上包络排序与序列处理单调栈数值计算与优化凸性/单峰性判定CF2200By

[Baltic2012]mobile

Mobile

题目描述

Totalphone 公司在一条新公路附近安装了若干通信基站。所有基站必须使用同一发射功率。为了尽可能节省用电,公司想知道覆盖整条公路至少需要多大的通信半径。

公路是从 (0,0)(0,0) 到 (L,0)(L,0) 的线段。对公路上的每一个点,取它与最近基站之间的欧几里得距离。求这些距离的最大值。公路上的点可以是端点,坐标也可以不是整数。

输入格式

第一行包含两个整数 N,LN,L,表示基站数和公路长度。

接下来 NN 行,第 ii 行包含两个整数 xi,yix_i,y_i,给出第 ii 座基站的坐标。所有坐标互不相同,按 xix_i 从小到大排列。若 xix_i 相同,按 yiy_i 从小到大排列。

输出格式

输出一行一个实数,表示所求的最大距离。绝对误差不超过 10−310^{-3} 即可。

样例 #1

2 10
0 0
11 1
5.545455

两座基站的中垂线与公路相交,最大距离在这个交点处达到。

数据范围

1≤N≤1061\le N\le 10^6,1≤L≤1091\le L\le 10^9,−109≤xi,yi≤109-10^9\le x_i,y_i\le 10^9。

原赛中,N≤5000N\le 5000 的数据共 2525 分,N≤105N\le 10^5 的数据共 5050 分。原题提示至少使用双精度浮点运算。