Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Roofing It
Description Bill Eaves owns the The architect's plans for the roof come in the form of a series of y) 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 (_{i}x, _{i}y) points lie on or below the new roof, and 2) to minimize the maximum vertical distance between any of the original (_{i}x, _{i}y) 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._{i}Input Input will consist of multiple test cases. Each case will begin with two positive integers y, specifying the _{i}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 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator