hdu3756(三分)

题意:三维坐标轴,有以原点为圆心,底面在xoy平面上,顶点在z轴上的圆锥,问圆锥的最小体积为多少才能完全覆盖空间里的所有点(n<=10000)

分析:

   很容易想到转成二维问题,将其投影到xoz平面,然后再把x负半轴的对称到x正半轴

   问题就变成了找一条直线和xoz第一象限交成个三角形,这个三角形面积最小且覆盖所有点

   肯定这条线过一个给定点

   考虑这样的子问题:过一个定点作直线交两个坐标轴成三角形,三角形面积随截距的变化肯定是个单峰函数

   我们考虑枚举H,对于固定的H,枚举这条直线经过哪个点,然后得到R,取最大的R就是能覆盖所有点的R

   一群单峰函数取max得到的也是单峰函数!

   所以可以直接三分H!

原文地址:https://www.cnblogs.com/wmrv587/p/6671346.html