LINELAND  Lineland Airport
Lineland is a strange country. As the name suggests, it's shape (as seen from above) is just a straight line, rather than some twodimensional shape. The landscape along this line is very mountainous, something which occasionally leads to some problems. One such problem now occurs: in this modern era the king wants to build an airport to stimulate the country's economy. Unfortunately, it's impossible for airplanes to land on steep airstrips, so a horizontal piece of land is needed. To accommodate for the larger airplanes, this strip needs to have length at least L.
Over the years, the inhabitants of Lineland have become very proficient in flattening pieces of land. Given a piece a land, they can remove rock quickly. They don't want to add rock for that may lead to an unstable landing strip. To minimize the amount of effort, however, they want to remove the least amount of rock necessary to reach their goal: a flat piece of land of length L. What is this minimum amount? Because of the lowdimensional nature of Lineland, the amount of rock that needs to be removed is measured as the total area of land above the place where the landing strip is placed, rather than the volume (so in the Figure below, the amount of land removed is given by the lightly shaded area).
Input
One line with a positive number: the number of test cases (at most 25). Then for each test case:
 One line with an integer N, 2 ≤ N ≤ 500, the number of points, and an integer L, 1 ≤ L ≤ 10000, the necessary length to flatten.
 N lines with two integers x_{i} and y_{i} with 0 ≤ x_{i}, y_{i} ≤ 10000 describing the landscape of Lineland. The x_{i} are in (strictly) ascending order. At position x_{i} the height of the landscape is x_{i}. Between two x_{i} the landscape has constant slope. (So the landscape is piecewise linear). The difference between x_{N} and x_{1} is greater than or equal to L.
Output
For each test case, output one line with the minimum amount of rock which must be removed in order to build the airport. The answer should be given as a floating point number with an absolute error of at most 10^{3}.
Example
Input: 4 3 5 0 2 4 2 14 0 4 3 0 2 2 0 4 0 5 3 3 10 10 2 30 2 35 7 2 777 222 333 4444 5555 Output: 0.9000 0.3750 0.0000 373362.4867
hide comments
meAnon:
20131210 08:05:25
How the answer for second test case is 0.3750 instead of 0.5000? 

Miodrag Milenkovic:
20090819 22:04:34
typo  in the input description, in the sentence "At position xi the height of the landscape is xi." the second xi should be yi. 
Added by:  overwise 
Date:  20071002 
Time limit:  3.450s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM ICPC NWERC 2006 