OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【ZJOI2008】瞭望塔

【题目描述】

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

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


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

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

【输入】

第一行包含一个整数n,表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数,为y1 ~ yn。

【输出】

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

【输入样例】

4
10 20 49 59
0 10 10 0

【输出样例】

14.500

【数据范围】

对于60%的数据,N≤60;

对于100%的数据,N≤300,输入坐标绝对值不超过10^6,注意考虑实数误差带来的问题。

【题解】

显然瞭望塔的塔顶位置一定在折线上方,具体在多上方,我们可以考虑半平面交,将折线的每一段所在直线的上方当作半平面,则它们的交集中任意一点都可以成为瞭望塔的塔顶。为了让答案最优,显然瞭望塔塔顶最终只会出现在半平面交交集的下凸壳上。

现在来找瞭望塔的位置,我们把折线和半平面交交集下凸壳看成两个分段一次函数,相减后即表示瞭望塔高度的函数,而这个函数的极值只会出现在分段的拐点或边界上。我们枚举折线的每个拐点和凸壳的每个顶点,计算对应的位置的瞭望塔高度,取最小值即可。

PS.数据范围里专门提示了考虑实数误差,其实精度完全不是问题,重要的是答案非常大,INF取到1e9都会WA_(:зゝ∠)_总之我一怒之下取到了1e30……以后这种题INF尽量取大一点吧,稳一点比较好~

【代码】

说了半天,代码其实很好写的~

http://paste.ubuntu.com/10779722/

评论

© OI技术宅 | Powered by LOFTER