eolymp
bolt
Try our new interface for solving problems
Məsələlər

Lonely Mountain

Lonely Mountain

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

"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

The plan of the Lonely Mountain consists of two parallel projections of the mountain to two projection planes. Both planes are perpendicular to the ground and each other. Each projection has a mountain-like shape.

Since Bilbo Baggins has never seen the mountain, he tries to imagine it. Is it really the Lonely Mountain or some ridges and other mountains surround it? In any case, it must be tremendous to hold the whole dwarves’ kingdom!

Bilbo decided to estimate the maximum possible volume of the Lonely Mountain and nearby mountains (if any) based on the plan provided by Gandalf.

Giriş verilənləri

The first line contains single integer number n_x — the number of points in the parallel projection of the mountain to the plane Oxz (2n_x100000). The second line contains n_x pairs of integer numbers x_i, z_i — the coordinates of the polygonal chain, representing the projection (-10^9x_1 < x_2 < x_3 < ... < x_nx10^9, 0z_i10^9, z_1 = z_nx = 0).

The following two lines contain projection to the Oyz plane in the same format.

Çıxış verilənləri

The only line of the output file must contain a single number V — the maximum possible volume of the Lonely Mountain.

The absolute or relative precision of you answer should be at least 10^{-6}. E.g. if V' is the actual maximum possible volume, the following must hold: .

If there are no mountains corresponding to the given projections, output a single line "Invalid plan".

Nümunə

Giriş verilənləri #1
6
0 0 1 1 2 0 3 3 4 4 6 0
5
0 0 1 1 2 1 3 4 4 0
Çıxış verilənləri #1
21.824074074074073
Giriş verilənləri #2
3
-1 0 0 1 2 0
4
0 0 1 1 2 2 3 0
Çıxış verilənləri #2
Invalid plan
Mənbə ACM ICPC 2013–2014, NEERC, Northern Subregional Contest, St Petersburg, October 26, 2013