PKU3127 Lineland's Airport

Lineland 是一个形状奇特的国家。顾名思义，从上空看，它并不是二维区域，而是一条直线。这个国家地势崎岖、山脉众多，因此常常遇到一些特殊的问题。

为了促进经济发展，国王计划修建一座机场。然而，飞机无法在陡峭的跑道上起降，因此需要开辟一段水平的土地。为了容纳大型飞机，这段跑道的长度至少应为 $L$。

Lineland 的居民擅长通过移除岩石来平整土地，但他们不愿填入岩石，因为这可能使跑道结构不稳定。现在需要选择一段长度至少为 $L$ 的连续土地，将其削平为水平跑道，并使移除的岩石量最少。

由于 Lineland 是一维的，移除的岩石量用原地形与跑道之间的总面积衡量，而不是体积。请计算修建机场所需移除岩石的最小面积。

输入格式

第一行包含一个正整数，表示测试用例的数量。

对于每组测试用例：

• 第一行包含两个整数 $N$ 和 $L$，其中 $N$ 表示描述地形的点数，$L$ 表示需要平整的最小长度；
• 接下来 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示地形在位置 $x_i$ 处的高度为 $y_i$。

所有 $x_i$ 严格递增。任意两个相邻给定点之间的地形斜率保持不变，因此整个地形是一条分段线性折线。

输出格式

对于每组测试用例，输出一行一个浮点数，表示修建机场所需移除岩石的最小面积。

答案的绝对误差不得超过 $10^{-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.900000
0.375000
0.000000
373362.486736

数据范围

• 测试用例数量不超过 $25$；
• $2\le N\le 500$；
• $1\le L\le 10^4$；
• $0\le x_i,y_i\le 10^4$；
• $x_1<x_2<\cdots<x_N$；
• $x_N-x_1\ge L$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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.900000
0.375000
0.000000
373362.486736