详情见:最近点对问题描述
- 由于设置本题的 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; }