프로그램 명: boi_mobile(special judge)
제한시간: 1 초
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 up individually for the stations, but one can only
set the transmission power to a fixed common value for all the stations. In order to
minimize power consumption, the company wants to know the maximal distance of
a point on the highway to the nearest base transceiver station.
입력
-
The first line consists of two integers N(1 ≤ N ≤ 10^6) and L(1 ≤ L ≤ 10^9) representing the number of base transceiver stations and the length of the highway, respectively.
-
N lines follow, each containing a pair of integers xi , yi (-10^9 ≤xi ,yi≤10^9) which describes the coordinates of a base transceiver station. All
points are distinct. Coordinates are sorted in the non-decreasing order with respect
to xi coordinates. If two values of xi are the same, then coordinates are sorted with
respect to yi coordinates in increasing order.
The highway is a straight line ranging from (0; 0) to (L; 0).
출력
The first and only line of the text file mobile.out should contain a single number -
the maximal distance of 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.
입출력 예
입력
2 10
0 0
11 1
출력
5.545455
Grading
-
Test cases where N≤5000 are worth 25 points.
-
Test cases where N≤100000 are worth 50 points.
Warning
Use at least double precision floating point numbers for your computations, as
smaller types may fail to give the precision required for solving the problem.
출처:boi 2012
special judge:ainta
[질/답]
[제출 현황]
[푼 후(0)]