(RankList for this Question)
Scooby-Doo is lost in one of the by-lanes of the street, Shaggy could not find him and knows he would be hungry so he has left N treats all over the street at random spots. Let us say, that Scooby-Doo is at point O, and we know the distances at which the treats are located at from point O.
Each treat can give Scooby energy to travel distance X, and if he can smell another treat within a distance X ahead, he can travel a further distance X just being motivated by the smell of the treat.
What distance should he be able to travel by eating each treat so that he can reach Shaggy without fainting?
(Upon eating a treat he loses all the energy he had before that and the only has the energy left is that of the treat he just ate)
Hint: It is a one-dimensional space and the treat has the power to attract Scooby X distance before and give him energy for further distance X. It forms a radius of influence where it can act. What should be the radius of influence of a treat?
The first line contains two integers N, D — the number of candies and the length of the street respectively.
The next line contains N integers ai (0 ≤ ai ≤ D). Multiple candies can be located at the same point. The candies may be located at the ends of the street.
Print the minimum distance X, needed to travel the whole street. The answer will be considered correct if its absolute or relative error doesn't exceed 10^-9. Please ensure you print 9 places after the decimal point.
15 5 3 7 9 14 0
Consider the first example, the candies are at a distance: 15, 5, 3, 7, 9, 14, 0 from where Scooby initially starts. The maximum distance between candies is 5.
Consider the second sample. At d = 2 the first treat will be eaten in the segment [0, 4], and the second one in segment [3, 5].
Log In to solve the Question