#1038. [ZJOI2008]瞭望塔

[ZJOI2008]瞭望塔

题目描述

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

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

我们可以用一条山的上方轮廓折线 (x1,y1),(x2,y2),,(xn,yn)(x_1, y_1), (x_2, y_2), \cdots,(x_n, y_n) 来描述 H 村的形状,这里 x1<x2<<xnx_1 < x_2 <\cdots< x_n。瞭望塔可以建造在 x1xnx_1\sim x_n 间的任意位置,但必须满足从瞭望塔的顶端可以看到 H 村的任意位置。可见在不同的位置建造瞭望塔,所需要建造的高度是不同的。为了节省开支,dadzhi 村长希望建造的塔高度尽可能小。

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

输入格式

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

接下来第一行n个整数,为 x1xnx_1\sim x_n。 第三行 nn 个整数,为 y1yny_1\sim y_n

输出格式

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

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

数据规模与约定

对于 60%60\% 的数据,1n601\le n\le60

对于 100%100\% 的数据,1n3001\le n\le 300,输入坐标绝对值不超过 10610^6,注意考虑实数误差带来的问题。