hdu3756（三分）
2024-09-30 18:06:00
题意：三维坐标轴，有以原点为圆心，底面在xoy平面上，顶点在z轴上的圆锥，问圆锥的最小体积为多少才能完全覆盖空间里的所有点(n<=10000)
分析：
很容易想到转成二维问题，将其投影到xoz平面，然后再把x负半轴的对称到x正半轴
问题就变成了找一条直线和xoz第一象限交成个三角形，这个三角形面积最小且覆盖所有点
肯定这条线过一个给定点
考虑这样的子问题：过一个定点作直线交两个坐标轴成三角形，三角形面积随截距的变化肯定是个单峰函数
我们考虑枚举H，对于固定的H，枚举这条直线经过哪个点，然后得到R，取最大的R就是能覆盖所有点的R
一群单峰函数取max得到的也是单峰函数！
所以可以直接三分H！
最新文章
- JVM内存管理&GC
- angular开发者吐槽react+redux的复杂：“一个demo证明你的开发效率低下”
- Dbcp2抛出org.apache.commons.dbcp2.LifetimeExceededException
- 【转】 利用.dSYM和.app文件准确定位Crash位置
- 两种局部刷新UITableView的方法的使用条件
- MySQL内存----使用说明全局缓存+线程缓存） 转
- thinkphp学习笔记2—入口文件
- LeetCode之Max Points on a Line Total
- New Year Tree 【DFS序+先段数区间查询修改+二进制保存状态】
- 不自动切换eclipse视图
- Linux-使用patch命令给uboot打补丁(3)
- HDU 3595 GG and MM [Every-SG]
- presto 函数中使用子查询
- MFC程序执行后台操作时不允许操作界面的一种方法
- Mac Apache WebDav 服务器配置
- jmeter解决登录token获取
- odoo创建编号
- websocket协议及案例
- WPF ControllTemplate Triggers小记 - 简书
- mysql(表类型的选择)