Mobile#4046
The well-known mobile network operator Totalphone has set up a number of new base transceiver stations in order to cover a newly built highway with its network. As always, the programmers of Totalphone have been sloppy; as a result, the transmission power cannot be set individually for the stations, but can only be set to a fixed common value for all the stations. In order to minimize power consumption, the company wants to know the maximal distance from a point on the highway to the nearest base transceiver station.
The first line of the input file consists of two integers (1 \leq N \leq 10^6) and (1 \leq L \leq 10^9), representing the number of base transceiver stations and the length of the highway, respectively. lines follow, each containing a pair of integers x_i, y_i (-10^9 \leq x_i, y_i \leq 10^9), which describe the coordinates of a base transceiver station. All points are distinct. Coordinates are sorted in non-decreasing order with respect to x_i coordinates. If two values of x_i are the same, then coordinates are sorted with respect to y_i coordinates in increasing order.
The highway is a straight line ranging from to .
The first and only line of the output file should contain a single number—the maximal distance from a point on the highway to the nearest base transceiver station. Your output will be regarded as correct if it differs by at most 10^{-3} from the precise result.
Example 1