eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ванна

Ванна

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Молодожены-программисты пришли в магазин выбирать ванну и обнаружили, что из-за сложной формы дна ванн непонятно, на какую высоту поднимается вода в каждой их них, если наливать одинаковый объем воды. Тогда они сфотографировали ванны с разных ракурсов и дома занялись компьютерным моделированием. Достаточно скоро они построили триангуляции поверхностей ванн, осталось только рассчитать высоту воды при заданном объеме.

Все построенные триангуляции поверхностей являются односвязными и содержат только такие треугольники, проекции которых на плоскость XY не пересекаются и не вырождаются в отрезок. Кроме того, дно ванны не содержит локальных максимумов и горизонтальные участки могут быть только на максимальной глубине. Для упрощения описания ванн молодожены не стали задавать внешние вертикальные границы, считая, что заданная поверхность окружена вертикальными стенками, верхняя кромка которых совпадает с нулевой глубиной.

Входные данные

В первой строке находятся два натуральных числа, разделенных не менее чем одним пробелом: n (1 n 200) – число вершин триангуляции и m (1 m 400) - число треугольников. В каждой из следующих n строк заданы вершины триангуляции, по 3 вещественных числа в строке, координаты в метрах, диапазон значений каждой координаты от 0 до 10, третья координата означает глубину в точке. В каждой из следующих m строк заданы треугольники, по 3 натуральных числа в строке, каждое число – порядковый номер вершины триангуляции. В последней строке одно натуральное число – объем наливаемой воды, измеряемый в литрах. Вода всегда наливается так, чтобы высота подъема не превышала максимальной глубины ванны.

Выходные данные

Вывести одно действительное число, округленное до трех десятичных знаков в формате с фиксированной точкой - высоту подъема воды относительно самой глубокой точки ванны.

Пример

Входные данные #1
4 2
0 0 1
1 0 1
0 1 1
1 1 1
1 2 3
2 3 4
10
Выходные данные #1
0.010
Источник 2013 Новосибирск, Май 5, Задача B