当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1974:Lineland's Airport

题目描述
Lineland is a strange country. As the name suggests, it抯 shape (as seen from above) is just a straight line, rather than some two-dimensional 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抯 economy. Unfortunately, it抯 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抰 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 low-dimensional 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).
输入解释
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 <= 10 000, the necessary length to flatten.
?N lines with two integers xi and yi with 0 <= xi, yi <= 10 000 describing the landscape of Lineland. The xi are in (strictly) ascending order. At position xi the height of the landscape is yi. Between two xi the landscape has constant slope. (So the landscape is piecewise linear). The difference between xN and x1 is greater than or equal to L.
输出解释
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^(&#8722;3).
输入样例
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
输出样例
0.9000
0.3750
0.0000
373362.4867
来自杭电HDUOJ的附加信息
Recommend wangye

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 NWERC2006

源链接: HDU-1974

最后修改于 2020-10-25T22:49:26+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/1000MS(Java/Others) 65536/32768K(Java/Others)