Одинокая Гора
"This was made by Thror, your grandfather, Thorin",
he said in answer to the dwarves’ excited questions.
"It is a plan of the Mountain."
J. R. R. Tolkien. The Hobbit, or There and Back Again
План Одинокой Горы состоит из двух параллельных проекций горы на две проекционные плоскости. Обе плоскости перпендикулярны поверхности земли и друг другу. Каждая проекция имеет вид горы.
Поскольку Бильбо Багинс никогда не видел горы, он старается вообразить ее. Это действительно Одинокая Гора или другие хребты и горы окружают ее? В любом случае, это скорее всего потрясающе огромное царство гномов!
Бильбо решил оценить максимально возможный объем Одинокой Горы и близлежащих гор (если таковые имеются) на основе плана, предоставленного Гандальфом.
Входные данные
Первая строка содержит одно число n[x] - количество точек в параллельной проекции горы на плоскость Oxz (2 ≤ n[x] ≤ 100000). Вторая строка содержит n[x] пар целых чисел x[i], z[i] — координаты ломанной, задающей проекцию (-10^9 ≤ x[1] < x[2] < x[3] < ... < x[nx] ≤ 10^9, 0 ≤ z[i] ≤ 10^9, z[1] = z[nx] = 0).
Следующие две строки содержат проекцию на плоскость Oyz в том же формате.
Выходные данные
В одной строке вывести одно число V - наибольший возможный объем Одинокой Горы.
Абсолютная или относительная погрешность ответа должна не превосходить 10^(-6). То есть если V - действительно максимальный возможный объем, то имеет место неравенство: .
Если не существует горы, соответствующей заданным проекциям, то вывести одну строку "Invalid plan".