Have You Driven a Fjord Lately?#2681
As most of us know, the western Scandinavian coastline contains many small inlets from the sea known as fjords. Fjords have very steep sides, making travel along the coast somewhat tedious (though breathtaking) as roads must curve back and forth around them. The Fjord Accelerated Scandinavian Traffic Commission (FAST) decided to solve this problem by constructing a series of bridges across the fjords to reduce the travel distances. To save costs, FAST is using pre-constructed bridge units of length meter each, but due to funding restrictions, the total length of bridge that can be built is limited. Therefore, they would like to determine the optimal locations to install bridges to maximize the total length of road saved. For example, if a bridge of length meters is built that cuts off meters of old road, a savings of meters is realized. To simplify where to locate the bridges, FAST has decided to model each fjord as two line segments joining three points, as shown in the figure below.
All angles forming fjords are less than 180^{\circ}. Furthermore, for safety reasons, each bridge can span at most one fjord.
Input for each test case consists of two lines. The first line contains two positive integers and , indicating the number of fjords and the maximum total bridge length (in meters) that can be built. The next line contains 2n+1 pairs of integer coordinates for the fjords, where the last coordinate for fjord also serves as the first coordinate for fjord i+1. All coordinates are given in meters and are between and . The maximum values for and are and , respectively.
Input ends with a line containing .
For each test case, output a single line containing the case number, the total bridge length used, and the total savings for the optimal placement of the bridges, using the format shown below. All values should be in meters, and the savings value should be rounded to the nearest hundredth.
Example 1