博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu3756(三分)
阅读量:5075 次
发布时间:2019-06-12

本文共 370 字,大约阅读时间需要 1 分钟。

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

分析:

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

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

   肯定这条线过一个给定点

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

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

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

   所以可以直接三分H!

转载于:https://www.cnblogs.com/wmrv587/p/6671346.html

你可能感兴趣的文章
Lua学习(1)——table
查看>>
Latex EPS 免费软件
查看>>
《CoderXiaoban》第八次团队作业:Alpha冲刺5
查看>>
HDFS的shell操作
查看>>
计算机网络HTTP、TCP/IP包
查看>>
python -- 字符串操作
查看>>
sscanf函数的高级用法
查看>>
使用友元,编译出错fatal error C1001: INTERNAL COMPILER ERROR (compiler file 'msc1.cpp', line 1786) 的解决...
查看>>
Codeforces 392-C Yet Another Number Sequence (矩阵快速幂)
查看>>
Spring AOP代理时 ClassCastException: $Proxy0 cannot be cast to (类型转换错误)
查看>>
discuz 数据调用
查看>>
学习OpenCV——Surf(特征点篇)&flann
查看>>
机器学习中导数最优化方法(基础篇)
查看>>
idea快捷生成
查看>>
python编辑选课系统
查看>>
PHP【curl】专题
查看>>
Ubuntu12.04 Installation and Subversion(svn)
查看>>
SSIS数据转换组件_聚合转换
查看>>
进程通信之信号量的操作
查看>>
最基础、最全面的iOS面试题目
查看>>