407897: GYM102920 G Mobile Robot

Mobile robots are nowadays commonly used in various industrial and research sites. You are in charge of controlling $$$n$$$ mobile robots that explore a very long, narrow and straight cave, which can be seen just as a line. The mobile robots collect data from the environment nearby and have effective mobility with their caterpillar tracks. You can control the $$$n$$$ mobile robots on your control desk by a wireless control system. The $$$n$$$ mobile robots you are controlling are labelled with numbers $$$1$$$ to $$$n$$$, and are identified by robot $$$1$$$, robot $$$2$$$, ..., robot $$$n − 1$$$, and robot $$$n$$$.

The mobile robots can also share their collected data to each other by a simple infrared communication protocol, while this robot-to-robot communication only works when the following very strict arrangement is completed for all the $$$n$$$ mobile robots: the distance between robot $$$i$$$ and robot $$$i + 1$$$ should be exactly d for all $$$i = 1, 2, \ldots , n − 1$$$, where $$$d$$$ is a prescribed positive real number, and no two robots should be at the same location in the cave. The location of each mobile robot in the cave is represented by a real number $$$x$$$ since the cave is very long, very narrow, and very straight, so can be considered a line which stretches limitlessly in both directions. The distance between two mobile robots is thus calculated by the difference of their locations.

From the current locations of the mobile robots, they now need to share data to each other, and you are going to move them for the robot-to-robot communication. Since the robots are slow and simultaneously move at the same speed along the cave, you want to minimize the maximum distance each robot should travel to waste as little time as possible. During traveling, any two robots are assumed to safely pass by each other at the moment when both are at a common location in the cave. Note hence that currently two or more robots may be at a common location in the cave.

Given the current locations of the $$$n$$$ mobile robots, write a program that computes their new locations for the robot-to-robot communication that minimizes the maximum distance each of the $$$n$$$ robots travels and outputs the minimized maximum distance the robots should travel.

Your program is to read from standard input. The input consists of exactly two lines. The first line consists of two integers, $$$n$$$ and $$$d$$$ ($$$2 \leq n \leq 1,000,000$$$ and $$$1 \leq d \leq 10^{10}$$$), where $$$n$$$ denotes the number of mobile robots you are controlling and $$$d$$$ is the distance that the robots should keep for the robot-to-robot communication. Each mobile robot is identified by a label from $$$1$$$ to $$$n$$$. The second line consists of $$$n$$$ integers, each of which ranges from $$$−10^{16}$$$ and $$$10^{16}$$$, representing the current locations of robot $$$1$$$, robot $$$2$$$, ..., and robot $$$n$$$ in this order.

Your program is to write to standard output. Print exactly one line consisting of a real number, rounded to the first decimal place, that represents the minimum possible value of the maximum distance the mobile robots should travel for the robot-to-robot communication from the given current locations.

5 1
1 3 5 7 9

2.0

5 1
-10 -1 0 1 2

4.0

5 1
1 3 5 9 7

2.5

5 1
1 1 1 1 1

2.0