1 second
256 megabytes
standard input
standard output
Vanya walks late at night along a straight street of length l, lit by n lanterns.
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 lantern is at the point ai.
The lantern 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 lanterns.
Vanya wonders: what is the minimum light radius d should the lanterns have to light the whole street?
The first line contains two integers n, l (1 ≤ n ≤ 1000, 1 ≤ l ≤ 109) —
the number of lanterns and the length of the street respectively.
The next line contains n integers ai (0 ≤ ai ≤ l).
Multiple lanterns can be located at the same point. The lanterns may be located at the ends of the street.
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.
7 15 15 5 3 7 9 14 0
2.5000000000
2 5 2 5
2.0000000000
Consider the second sample. At d = 2 the first lantern will light the segment [0, 4] of
the street, and the second lantern will light segment [3, 5]. Thus, the whole street will be lit.
解题思路：
标准的贪心算法，只需要先开始对于区间上的每个灯笼的坐标从小到大进行排序，然后依次贪心下去，就能得到灯笼的最小半径了。
也就是说，我们开始只需要考虑第一个点和最后一个点的位置，因为这两个点的距离整个线段来说起着决定的作用（QAQ，自己脑补下，LRJ的风格）
那么，从第一个点到第n-1个点，我们找到能恰好相切的地方后，然后不断的更新ans的值，从题目本身来说是一个找最小半径的问题，但是就划分到
子区间来说，确是一个找最大覆盖的问题，所以分析好问题的本质就行。
代码：
# include<cstdio>
# include<iostream>
# include<algorithm>
using namespace std;
# define MAX 1234
double a[MAX];
int main(void)
{
int n,L;
while ( cin>>n>>L )
{
for ( int i = 1;i <= n;i++ )
cin>>a[i];
sort ( a+1,a+1+n );
double ans = a[1];
for ( int i = 1;i <= n-1;i++ )
{
ans = max( ans,(a[i+1]-a[i])/2*1.0 );
}
ans = max(ans,L-a[n]);
printf("%.10lf\n",ans);
}
return 0;
}