题目描述

"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.

输入格式

The first line contains single integer number $n_{x}$ -- the number of points in the parallel projection of the mountain to the plane Oxz $(2 \le n_{x} \le 100 000)$ . The second line contains $n_{x}$ pairs of integer numbers $x_{i}, z_{i}$ -- the coordinates of the polygonal chain, representing the projection $(−10^{9} \le x_{1} < x_{2} <$ x3 $< · · · < x_{n_{x}} \le 10^{9}; 0 \le z_{i} \le 10^{9}; z_{1} = z_{n_{x}} = 0)$ .

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

输出格式

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: $mi_n(|V−V′|,|V−V′|/V′) \le 10^{−6}.$

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

题目大意

给定一个几何体的正视图和侧视图，求其最大体积。

输入格式

第一行一个整数 $n_x$ 表示正视图中点的数量。

第二行按 $x_i$ 递增的顺序给出 $n_x$ 个点对 $(x_i,z_i)$ 描述其正视图，保证 $z_1=z_{n_x}=0$

第三、四行同理，描述其侧视图。

所有的输入都是整数。

输出格式

若不存在一个合法方案，输出 Invalid plan，否则输出最大体积。

你的答案与正确答案的绝对误差不应超过 $10^{-6}$.

6
0 0 1 1 2 0 3 3 4 4 6 0
5
0 0 1 1 2 1 3 4 4 0

21.824074074074074073

3
-1 0 0 1 2 0
4
0 0 1 1 2 2 3 0

Invalid plan

提示

Time limit: 2 s, Memory limit: 256 MB.