ALG4:最近点对(the closest pair of points )
2021/5/23 18:25:26
本文主要是介绍ALG4:最近点对(the closest pair of points ),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
ALG4:最近点对(the closest pair of points )
问题描述如下:
详情见:最近点对问题描述
具体实现:
- 由于设置本题的 OJ 设置了时间限制,规定了只能用分治的思想实现
- 分成三部分处理:
- 根据中值将待处理的点集分成三部分
- 左边求出最小值 d l e f t d_{left} dleft
- 右边求出最小值 d r i g h t d_{right} dright
- 中间的点带求出最小值 d m i d d_{mid} dmid,(根据鸽巢原理,中间的点带中需要求的点不会超过6个)
- 将左右两边的点集处理方式类似,递归求解子问题
具体的代码实现如下:
(已通过全部的23个测试样例)
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <math.h> using namespace std; class Point { public: double x; double y; Point() { x = 0.00; y = 0.00; } }; double dist(Point a, Point b) {//计算两个点之间的距离 return sqrt(double((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))); } bool cmp1(Point a, Point b) {//制定外层排序规则 return a.x < b.x; } bool cmp2(Point a, Point b) {//指定内层排序规则 return a.y < b.y; } double min_dist(Point* point_list, int left_index, int right_index) { //递归出口 if (right_index - left_index == 1) return dist(point_list[left_index], point_list[right_index]); //处理两边的情况 int mid_index = (left_index + right_index) >> 1; double min_left = min_dist(point_list, left_index, mid_index); double min_right = min_dist(point_list, mid_index, right_index); double d = min(min_left, min_right);//找到左右两边的最小距离 //下面找中间的点的最小值 vector<Point> mid_list; for (int left = mid_index; left >= left_index; left--) {//从中间开始向左找 if (point_list[mid_index].x - point_list[left].x <= d) mid_list.push_back(point_list[left]); else break; } for (int right = mid_index + 1; right <= right_index; right++) {//从中间开始向右找 if (point_list[right].x - point_list[mid_index].x <= d) mid_list.push_back(point_list[right]); else break; } sort(mid_list.begin(), mid_list.end(), cmp2); //对于中间节点序列进行处理 double min_mid = 0xffffffffffffffff; for (int i = 0; i < mid_list.size() - 1; i++) for (int j = i + 1; j < mid_list.size(); j++) if (mid_list[j].y - mid_list[i].y <= d) min_mid = min(min_mid, dist(mid_list[i], mid_list[j])); else break; return min(min_mid, d); } int main() { int n; cin >> n; Point* point_list = new Point[n]; for (int i = 0; i < n; i++) { double x, y; cin >> x >> y; point_list[i].x = x; point_list[i].y = y; } sort(point_list, point_list + n, cmp1); cout << fixed << setprecision(2) << pow(min_dist(point_list, 0, n - 1), 2) << endl; return 0; }
仅供复习时整理参考,用于学习交流
这篇关于ALG4:最近点对(the closest pair of points )的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享