CodeForces 492B

时间:2023-03-09 04:32:37
CodeForces 492B

Description

Vanya walks late at night along a straight street of length l, lit by n *s. Consider the coordinate system with the beginning of the street corresponding to the point 0, and its end corresponding to the point l. Then the i-th * is at the point ai. The * lights all points of the street that are at the distance of at most d from it, where d is some positive number, common for all *s.

Vanya wonders: what is the minimum light radius d should the *s have to light the whole street?

Input

The first line contains two integers nl (1 ≤ n ≤ 1000, 1 ≤ l ≤ 109) — the number of *s and the length of the street respectively.

The next line contains n integers ai (0 ≤ ai ≤ l). Multiple *s can be located at the same point. The *s may be located at the ends of the street.

Output

Print the minimum light radius d, needed to light the whole street. The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

Sample Input

Input
7 15 
15 5 3 7 9 14 0
Output
2.5000000000
Input
2 5 
2 5
Output
2.0000000000

Hint

Consider the second sample. At d = 2 the first * will light the segment [0, 4] of the street, and the second * will light segment [3, 5]. Thus, the whole street will be lit.

题意:一条街,起点0,长度L。在街上有多盏灯,每盏灯的照亮半径一样,求最小半径使得整个街道都是亮的...(可以一个位子放多盏灯,0和L点都可以放灯)

解题思路:    第一种情况,0和L都有放灯,那么答案就是求相邻两盏灯之间的最大距离的一半,因为只有这样才可能照亮整个街道。就可木桶原理差                                不多。

      第二种情况,首尾有可能没有放,或者只放了一个,就和案例2一样(位置0到第一个灯的距离为2大于用情况一求的0.5,所以答案就是                               2)

      这样的话 就可以总结下,只要求出相邻最大的距离的一半,然后和位置0到第一个灯的距离c1,以及最后一个灯到L的距离c2。他们进行                                    比较 ,最后输出他们三个中最大值就好了 

代码如下:(额 忘记说了 ,还要排个序.....)

 #include <stdio.h>
#include <algorithm>
using namespace std;
int a[];
int main()
{
int n,l,q,c1,c2;
while(scanf("%d%d",&n,&l)!=EOF)
{
double r=,ans=;
for(int i=; i<n; i++)
scanf("%d",&a[i]);
sort(a,a+n);
for(int i=; i<n; i++)
{
q=a[i]-a[i-];
if(q>r) r=q;
}
c1=a[];
c2=l-a[n-];
ans=max(c1,c2);
ans=max(r/,ans);
printf("%.10lf\n",ans);
}
return ;
}