La Montagna Solitaria#6271
«Lo fece Thror, tuo nonno, Thorin», "— rispose alle agitate domande dei nani. — È la pianta della Montagna".
— J. R. R. Tolkien, Lo Hobbit, ovvero Andata e ritorno
La pianta della Montagna Solitaria è costituita da due proiezioni parallele della montagna su due piani di proiezione. Entrambi i piani sono perpendicolari al terreno e tra loro. Ogni proiezione ha la forma di una montagna.
Bilbo Baggins non ha mai visto la montagna, perciò cerca di immaginarsela. È davvero un'unica montagna solitaria, oppure è circondata da catene montuose e da altre montagne? In ogni caso deve essere enorme, per poter contenere un intero regno dei nani!
In base alla pianta che gli ha consegnato Gandalf, Bilbo ha deciso di stimare il volume complessivo massimo possibile della Montagna Solitaria e delle montagne vicine, se presenti.
Nella prima riga è dato un numero intero n_x~(2 \le n_x \le 10^5) — il numero di punti nella proiezione parallela della montagna sul piano . Nella seconda riga sono date n_x coppie di numeri interi x_i, z_i — le coordinate dei vertici della spezzata che definisce la proiezione (-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).
Le due righe successive, nello stesso formato, descrivono la proiezione sul piano .
Stampate un numero — il volume massimo possibile della Montagna Solitaria.
La risposta deve avere un errore assoluto o relativo non superiore a 10^{-6}. In altre parole, se è il volume massimo possibile reale, deve essere soddisfatta la seguente condizione:
Se non esiste alcuna montagna corrispondente alle proiezioni date, stampate una singola riga Invalid plan.
Esempio 1
Esempio 2