New Year Tree Decorations

题意翻译

由于有一段作为一个信奉无神论的苏维埃国家的历史，俄国在20世纪的多数时候并不庆祝圣诞节。这导致了俄国人把庆祝圣诞和庆祝新年两个活动合二为一成了“新年”，并在同时成为一个含有挂圣诞树、有被称做“冰霜老爷爷”的形象、礼物赠送、阖家团圆和晚宴的全国性节日。 购买一棵树并把它种在房屋前面成了一种习俗。通常，整个家庭会在新年夜上在一起装扮这棵圣诞树。我们希望Codeforces也成为一个我们（心灵中的）有爱的大家庭，所以在这个问题中，我们也将装扮一棵树。 现在，我们的装饰包括n块。每一块是一块彩纸，它的边缘是一条有着特殊形状的封闭折线。图中，每一块彩纸都被单独展示了。 第i块是一条经过(0,0),(0,y0),(1,y1),(2,y2)...(k,yk)，(k,0)。 每一块纸的宽度都为k. 其中，彩纸将会按照序号从大到小叠放，编号最大的被叠放在最下面，最小的则在最上面。 程序员是一群好奇心很强的人，所以我们在进行的装饰的时候也想知道： 每一块纸的可见面积是多少？ 输入： 第一行包括两个整数n,m(1 <= n,k <= 300)。 接下来n行，每行包括k+1个整数，表示对封闭折线的描述。 如果第i行包括了$y_{i,0},y_{i,1},...y{i,k}$，表示第i块纸的封闭折线经过了点$(0,0),(0,y_{i,0}),(1,y_{i,1}),(2,y_{i,2})...(k,y_{i,k}),(k,0)$ $(1 <= y_{i,j} <= 1000)$ 输出： n个实数，依次表示每块纸的可见区域。 你的答案只要和标准答案差距不超过$10^{-4}$就被认为正确。

题目描述

Due to atheistic Soviet past, Christmas wasn't officially celebrated in Russia for most of the twentieth century. As a result, the Russian traditions for Christmas and New Year mixed into one event celebrated on the New Year but including the tree, a Santa-like 'Grandfather Frost', presents and huge family reunions and dinner parties all over the country. Bying a Tree at the New Year and installing it in the house is a tradition. Usually the whole family decorates the tree on the New Year Eve. We hope that Codeforces is a big and loving family, so in this problem we are going to decorate a tree as well. So, our decoration consists of $ n $ pieces, each piece is a piece of colored paper, its border is a closed polyline of a special shape. The pieces go one by one as is shown on the picture. The $ i $ -th piece is a polyline that goes through points: $ (0,0) $ , $ (0,y_{0}) $ , $ (1,y_{1}) $ , $ (2,y_{2}) $ , ..., $ (k,y_{k}) $ , $ (k,0) $ . The width of each piece equals $ k $ . The figure to the left shows the decoration, the figure to the right shows the individual pieces it consists of.The piece number 1 (shown red on the figure) is the outer piece (we see it completely), piece number 2 (shown yellow) follows it (we don't see it completely as it is partially closed by the first piece) and so on. The programmers are quite curious guys, so the moment we hung a decoration on the New Year tree we started to wonder: what area of each piece can people see?

输入输出格式

输入格式

The first line contains two integers, $ n $ and $ k $ $ (1<=n,k<=300) $ . Each of the following $ n $ lines contains $ k+1 $ integers — the description of the polyline. If the $ i $ -th line contains ontegers $ y_{i,0},y_{i,1},...,y_{i,k} $ , that means that the polyline of the $ i $ -th piece goes through points $ (0,0) $ , $ (0,y_{i,0}) $ , $ (1,y_{i,1}) $ , $ (2,y_{i,2}) $ , ..., $ (k,y_{i,k}) $ , $ (k,0) $ $ (1<=y_{i,j}<=1000) $ .

输出格式

Print $ n $ real numbers — for each polyline, the area of its visible part. The answer will be considered correct if its relative or absolute error do not exceed $ 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