← 返回题目列表

Codeforces · 379/E

E. 新年树装饰品

中文机器翻译题面 查看原题

由于苏联过去奉行无神论,二十世纪的大部分时间俄罗斯都没有正式庆祝圣诞节。结果,俄罗斯圣诞节和新年的传统融入了一项庆祝新年的活动,但包括圣诞树、圣诞老人般的“霜爷爷”、礼物以及全国各地的大型家庭聚会和晚宴。新年时栽一棵树并将其安装在房子里是一种传统。通常全家人都会在除夕夜装饰圣诞树。我们希望Codeforces是一个充满爱的大家庭,所以在这个问题中我们也将装饰一棵树。

那么,我们的装饰由n块组成,每块都是一张彩纸,它的边框是一条特殊形状的闭合折线。如图所示,这些碎片一件接一件地排列。第 i 段是一条经过以下点的折线:(0, 0)、(0, y0)、(1, y1)、(2, y2)、...、(k, yk)、(k, 0)。每块的宽度等于k。

左图显示了装饰,右图显示了其组成的各个部分。

编号 1 的部件(图中红色显示)是外部部件(我们完全看到它),编号 2 的部件(显示黄色)紧随其后(我们看不到它完全,因为它被第一块部分封闭),依此类推。程序员们都是好奇心很强的人,所以当我们在新年树上挂上装饰品的那一刻,我们就开始想:人们能看到每件装饰品的哪些区域?

输入

第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 300)。以下 n 行中的每一行都包含 k + 1 个整数——折线的描述。如果第 i 条线包含整数 yi, 0, yi, 1, ..., yi, k,则表示第 i 条折线经过点 (0, 0)、(0, yi, 0)、(1, yi, 1)、(2, yi, 2)、...、(k, yi, k)、(k, 0) (1 ≤ yi, j ≤ 1000)。

输出

打印 n 个实数 — 对于每条折线,其可见部分的面积。

如果答案的相对或绝对误差不超过 10 - 4,则认为答案是正确的。

示例

输入 #1

2 2
2 1 2
1 2 1

输出 #1

3.000000000000
0.500000000000

输入 #2

1 1
1 1

输出 #2

1.000000000000

输入 #3

4 1
2 7
7 2
5 5
6 4

输出 #3

4.500000000000
1.250000000000
0.050000000000
0.016666666667