Mobile Robot
Time limit1sMemory limit512 MB
Given n robot positions on a line, find the minimum possible maximum travel distance so that the robots end up spaced exactly d apart in some order.
- Level
Medium7 of 10
- Topics
- Binary search, Sorting, Greedy, Math
- Solved
- No attempts yet
Problem
Mobile robots are now common in many 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 simply as a line. The mobile robots collect data from the nearby environment and have effective mobility thanks to their caterpillar tracks. You can control the n mobile robots from your control desk with a wireless control system. The n mobile robots you control are labelled 1 to n and are identified as robot 1, robot 2, …, robot n − 1, and robot n.
The mobile robots can also share the data they collect with each other through a simple infrared communication protocol, but this robot-to-robot communication works only when the following very strict arrangement is completed for all n mobile robots: the distance between robot i and robot i + 1 must be exactly d for every i = 1, 2, … , n − 1, where d is a prescribed positive real number, and no two robots may 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 it can be treated as a line that stretches without limit in both directions. The distance between two mobile robots is therefore calculated as the difference of their locations.
The robots must now share data with each other from their current locations, and you will move them for the robot-to-robot communication. Since the robots are slow and move simultaneously at the same speed along the cave, you want to minimize the maximum distance each robot travels so as to waste as little time as possible. During travel, any two robots are assumed to pass by each other safely at the moment when both are at a common location in the cave. Note 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 new locations for the robot-to-robot communication that minimize the maximum distance each of the n robots travels, and outputs the minimized maximum travel distance.
Input
Your program reads input from standard input. The input consists of exactly two lines. The first line contains two integers n and d (2 ≤ n ≤ 1,000,000 and 1 ≤ d ≤ 10^10), where n is the number of mobile robots you control and d is the distance the robots must keep for the robot-to-robot communication. Each mobile robot is identified by a label from 1 to n. The second line contains n integers, each between −10^16 and 10^16 inclusive, representing the current locations of robot 1, robot 2, …, and robot n in this order.
Output
Your program writes output to standard output. Print exactly one line containing a real number, rounded to the first decimal place, that represents the minimum possible value of the maximum distance the mobile robots must travel for the robot-to-robot communication from the given current locations.