logo AlgoBeat OnlineJudge
登录 注册

#101038. [BZOJ 1038] [ZJOI2008]瞭望塔

内存限制:162 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

致力于建设全国示范和谐小村庄的 H 村村长 dadzhi,决定在村中建立一个瞭望塔,以此加强村中的治安。

我们将 H 村抽象为一维的轮廓。

我们可以用一条山的上方轮廓折线 来描述 H 村的形状,这里 。瞭望塔可以建造在 间的任意位置,但必须满足从瞭望塔的顶端可以看到 H 村的任意位置。可见在不同的位置建造瞭望塔,所需要建造的高度是不同的。为了节省开支,dadzhi 村长希望建造的塔高度尽可能小。

请你写一个程序,帮助 dadzhi 村长计算塔的最小高度。

输入格式

输入第一行包含一个整数 ,表示轮廓折线的节点数目。

接下来第一行n个整数,为 。 第三行 个整数,为

输出格式

输出仅包含一个实数,为塔的最小高度,精确到小数点后三位。

样例

样例输入 #1

6
1 2 4 5 6 7
1 2 2 4 2 1

样例输出 #1

1.000

数据范围与提示

对于 的数据,

对于 的数据,,输入坐标绝对值不超过 ,注意考虑实数误差带来的问题。