K :: T-cell Operator

Time Limit: 1 Second    Memory Limit: 32768 KB

T-cell operator which is famous for its T-shaped antennas is invited to launch a cellular network in a mountain range of Flatland, a well-known two-dimensional world. The mountain range can be modeled with a horizontal base line (y = 0) and an x-monotone polygonal terrain above the base line as depicted in the figure below. By x-monotone, we mean that the x-coordinate of the polygon vertices are in ascending order along the base line.
In the first step, T-cell gave the responsibility of overall planning and budget estimation to its operations committee (OC). The preliminary investigation of OC showed that developing several base stations (fixed-location transceivers also known as cell sites) is not economical as even a small piece of land is too expensive in the mountain range of Flatland. Fortunately, the mountain range is small enough to be totally covered by only one antenna, but the main problem is that T-cell uses signals which are unable to pass through solid objects (specifically the mountains here), i.e. one can communicate with the base station only if she can directly see at least a point of the antenna installed at the base-station.
As T-cell has got its world recognition due to the lack of any blind spot in its coverage, the final plan of OC is to install a T-shaped antenna (symmetric to its mast) with adjustable mast height h and the fixed head size k such that any point of the mountain range can see at least a point of the antenna. The antenna of course should not interiorly intersect the terrain. Touching the mountains is permitted though.
To make the plan economical, OC is now looking for a spot of the mountain range as the base station that minimizes ? (the height of the antenna, where every point of the terrain can see at least one point of the antenna). And, that’s why they have hired you; given the shape of the mountain range and the length ? as the fixed head size of the antenna, find the optimum position of the base station with the minimum possible height h for its antenna.

Input

The input contains several test cases. Each test case starts with a line containing two space-separated integers n (2 <= n <= 1000), the number of the vertices of the polygonal terrain, and k (0 <= k <= 10⁵), the head size of the antenna. Next, the description of the terrain comes in n lines, one line per vertex. More precisely, the i^th line of this block contains two space-separated integers x_i and y_i (0 <= x_i, y_i <= 10⁵), the coordinates of the i^th vertex (from the left) of the polygonal terrain, and indeed, the border of the mountain range can be obtained by connecting these consecutive vertices. It is guaranteed that x₁ < x₂ < ... < x_n, and the first and the last vertices of the terrain are not a peak (i.e. y₁ < y₂ and y_n-1 > y_n). You can also assume that the line passing through each edge of the polygon does not intersect the line segment connecting the points (0, 10⁸) and (10⁵,10⁸).
The input terminates with a line of the form '0 0' (omit the quotes) which should not be considered as a test case.

Output

For each test case, write a line containing the real number h, the minimum possible height of antenna for that position,
rounded to exactly 2 digits after the decimal point.

Sample Input

5 2
1 1
2 2
3 1
4 2
5 1
4 1
1 0
2 2
5 2
6 1
5 4
1 1
2 3
4 1
5 2
6 0
0 0

Sample Output

1.00
1.33
0.50

Submit

Source: Tehran, Asia Region - Regional 2011