参考资料:
给出一个平面内所有点的坐标, 求出这些点中最近的两个点的距离
此时, 原问题转化成了3个子问题:
对于子问题1, 2而言, 问题的规模相较于原问题显然减少了一半. 有两种让递归终止的条件:
ans
不变a
和b
, 此时将答案更新为原答案ans
和a
与b
之间距离的较小者.对于子问题3而言, 我们可以采用如下方法缩小问题规模:
ans
的点, 将这些点的序号保存在一个临时的数组里.#include<iostream> #include<algorithm> #include<cmath> #include<stdio.h> using namespace std; const double INF =1e15; //设定一个足够大的初始值 class point { public: double x, y; public: bool operator <(const point b) { if (x==b.x) return y < b.y; else return x < b.x; } }; point arr[100005]; int temp[100005]; double ans = INF; int n; bool cmp(int a, int b) { return arr[a].y < arr[b].y; } double dis(const point& a, const point& b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } void closest(int L, int R) { if (L >= R) return; else if (R - L == 1) { ans = min(ans, dis(arr[L], arr[R])); return; } int mid = (L + R) >> 1; closest(L, mid - 1); closest(mid + 1, R); int cnt = 0; for (int i = L; i <= R; i++) { if (fabs(arr[i].x - arr[mid].x) <= ans) temp[cnt++] = i; } sort(temp, temp + cnt, cmp); for (int i = 0; i < cnt; i++) { for (int j = i + 1; j < cnt; j++) { if (arr[temp[j]].y - arr[temp[i]].y > ans) break; ans = min(ans, dis(arr[temp[i]], arr[temp[j]])); } } } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> arr[i].x >> arr[i].y; sort(arr, arr + n); closest(0, n - 1); printf("%.4lf", ans); return 0; }