Самотня Гора#6271

Самотня Гора

2 секунди

256 мегабайтів

Дуже складна

План Самотньої гори складається з двох паралельних проєкцій гори на дві площини проєкцій. Обидві площини перпендикулярні землі та одна одній. Кожна проєкція має форму гори.

Більбо Беггінс ніколи не бачив гору, тому намагається уявити її собі. Чи справді це одна-єдина самотня гора, чи її оточують хребти та інші гори? У будь-якому разі вона має бути величезною, щоб вмістити ціле гномське королівство!

За планом, який передав йому Гендальф, Більбо вирішив оцінити максимально можливий сумарний об'єм Самотньої гори та сусідніх гір, якщо вони є.

Вхідні дані

У першому рядку задано ціле число $n_{x} (2 \leq n_{x} \leq 1 0^{5})$ n_x~(2 \le n_x \le 10^5) — кількість точок у паралельній проєкції гори на площину $O x z$ . У другому рядку задано $n_{x}$ n_x пар цілих чисел $x_{i}, z_{i}$ x_i, z_i — координати вершин ламаної, що задає проєкцію $(- 1 0^{9} \leq x_{1} < x_{2} < x_{3} < \dots < x_{n_{x}} \leq 1 0^{9}, 0 \leq z_{i} \leq 1 0^{9}, z_{1} = z_{n_{x}} = 0)$ (-10^9 \leq x_1 < x_2 < x_3 < \ldots < x_{n_x} \le 10^9, 0 \le z_i \le 10^9, z_1 = z_{n_x} = 0).

Наступні два рядки в тому самому форматі описують проєкцію на площину $O y z$ .

Вихідні дані

Виведіть одне число $V$ — максимально можливий об'єм Самотньої гори.

Відповідь повинна мати абсолютну або відносну похибку не більше ніж $1 0^{- 6}$ 10^{-6}. Іншими словами, якщо $V$ — справжній максимально можливий об'єм, то має виконуватися умова:

min (∣ V - V^{'} ∣, \frac{∣ V - V ^{'} ∣}{V ^{'}}) \leq 1 0^{- 6}

\min\left(|V - V'|, \frac{|V - V'|}{V'}\right) \le 10^{-6}

Якщо не існує гір, що відповідають заданим проєкціям, виведіть один рядок Invalid plan.

Приклади

Приклад 1

Приклад 2