编程之美 set 6 寻找最近点对
2024-09-28 19:49:52
这道题在算法课上当做例题讲过, 当时的印象也比较深
另有一道近似算法的题也在算法课上讲过, 并且印象更深, 复习的时候完全没管, 以为志在必得, 结果真考了那道近似算法, 我却没能打出来
为避免阴沟翻船, 寻找最近点对还要再回顾一下
算法
核心是分治算法
1. 分别根据点的 x,y 值进行排序
2. 在 x 轴上划一道垂线, 将点均分成两半
3. 假设最近点对都在左/右部分, 递归计算左/右半部分的最短距离并返回较小值 dis
4. 假设最近点对分别在左右两个部分, 横跨中心的竖线. 中心线为中心, 2*dis 为宽度画一个矩形, 横跨中心线的最近点对 candidate 都在这个矩形内. 将这些点按照 y 值的大小加入到数组中. 遍历数组中的点, 将该点与其后的 7 个点计算距离, 返回最小距离
5. 为什么仅和 7 个点作对比呢. 因为已经假设 dis 是左右不分最近点对的最小值, 这就说明在一个长(宽)为 dis 的正方形内, 至多有 4 个点. 长为 dis*2, 宽为 dis 的长方形至多 8 个.
最新文章
- JavaScript 中 onload 事件绑定多个方法
- 软件测试人员必备Linux命令(初、中、高级)
- phpstorm 实用快捷键 和 注释
- poj1012约瑟夫
- 供应商 银行 SQL (转自ITPUB)
- Java中接口作为方法的返回
- oracle max()函数和min()函数
- 13个Cat命令管理文件实例汇总
- 糟糕的双重检查加锁(DCL)
- SqlServer将日期格式DateTime转换成varchar类型
- O-C浮点数转化整数
- 7_SQL Server通过代码删除数据
- WinForm中ClickOnce发布至广域网
- python正则表达式--分组、后向引用、前(后)向断言
- .NET CORE学习笔记系列(2)——依赖注入[4]: 创建一个简易版的DI框架[上篇]
- Spring Bean自动检测
- 命令查看linux主机配置
- WPF Demo12 布局
- 吴裕雄 17-MySQL 排序
- Get、Post 提交的乱码问题
热门文章
- [精]Oracle APEX 5.0 入门教程(一) Form表单
- Apach 配置虚拟机时候DocumentRoot参数最后不要加斜杠
- 基于Redis构建10万+终端级的高性能部标JT808协议的Gps网关服务器(转)
- Atitit. 软件GUI按钮与仪表盘--web服务器区--获取apache配置文件路径 linux and apache的启动、停止、重启
- Nginx 0.8.x + PHP 5.2.13(FastCGI)搭建胜过Apache十倍的Web服务器(第6版)[原创]
- Python|PyCharm安装scrapy包
- vss安装及服务器端、客户端配置图文教程
- hdu1978(记忆化搜索)
- gdb 初步学习记录
- 分布式模式之Broker模式(转)