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;
}