Description
Bill Eaves owns the Shingle Minded roofing company which is a sub-contracting firm specializing in putting roofs on buildings. Often, Bill will receive a design for a roof from some young hot-shot architect which, though it may have some aesthetic appeal, is totally impractical. In these cases, Bill will begin negotiations with the architect and the client to find a simpler design. Bill's only concern is that the roof be convex, to allow rain, snow and frisbees to roll off easily. The architect's main concern is that the maximum height between his original roof and the compromise roof be as small as possible. The client's main concern is to get out of this meeting as soon as possible and get back to watching TV.
The architect's plans for the roof come in the form of a series of n points (xi, yi) specifying the outline of the roof as seen from the side of the house. The roofs are always symmetrical, so the architect only shows the front side of the roof (from its start at the front of the house to its peak). Once Bill gets these plans and a decision is made on how many sections the convex roof should have, he must decide how to place the sections so as to 1) make sure that all the original (xi, yi) points lie on or below the new roof, and 2) to minimize the maximum vertical distance between any of the original (xi, yi) points and the new roof. All sections must lie on at least two of the initial points specified by the architect. An example is shown below. On the left are the initial points from the architect. The next two pictures show an approximation of the roof using only two sections. While both of these are convex, the second of the two is the one which minimizes the maximum distance.
Input
Input will consist of multiple test cases. Each case will begin with two positive integers n and k (2 ≤ n ≤ 100, 1 ≤ k < n) indicating the number of points used in the original roof plan and the number of sections used in the compromise roof. These will be followed by n lines each containing two floating points numbers xi yi, specifying the n points in the roof plan. These values will be given in increasing order of x, and the last point will be guaranteed to have the highest y value of any of the points. All values will be between 0.0 and 10000.0. The last case is followed by a line containing 0 0 which indicates end-of-input and should not be processed.
Output
For each test case, output the maximum distance between the best compromise roof and the initial points, rounded to the nearest thousandth.
Sample Input
6 2
0.0 0.0
1.0 3.0
3.0 6.0
6.0 9.0
8.0 10.0
17.0 12.0
0 0
Sample Output
1.500
