Roof Construction
Time limit2sMemory limit128 MB
Given N points and a limit K, find the minimum vertical offset needed so a concave polyline with at most K segments lies on or above every point.
- Level
Hard8 of 10
- Topics
- Geometry, Binary search, Greedy, Dynamic programming
- Solved
- No attempts yet
Problem
An architect wants to revise a roof profile designed by a designer so that rain and snow can slide off a convex shape.
The N input points are reference points of the original roof design. Treat the new roof as one polygonal chain drawn over the x-coordinate range of those points. Because the roof is the upper boundary of a convex polygon, the slopes of its segments must not increase from left to right. The roof may contain at most K line segments.
Every input point must lie on or below the new roof. For a point (x, y), let R(x) be the y-coordinate of the new roof at the same x-coordinate. The difference at that point is R(x) - y, and the total difference is the maximum of that value over all input points.
Given the points and K, compute the minimum possible total difference.
Input
The first line contains the number of points N and the maximum number of segments K. (1 <= N <= 100, 1 <= K <= N)
Each of the next N lines contains the coordinates x and y of one point. Both x and y are decimal numbers between 0 and 10000, inclusive.
Output
Print the minimum possible total difference, rounded to three digits after the decimal point.