| Good Bye 2013 |
|---|
| Закончено |
В России традиционно на новый год люди покупают и ставят себе в дом елку. Наряжают елку перед праздником обыкновенно всей семьей. 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.
2 2
2 1 2
1 2 1
3.000000000000
0.500000000000
1 1
1 1
1.000000000000
4 1
2 7
7 2
5 5
6 4
4.500000000000
1.250000000000
0.050000000000
0.016666666667
