n2的暴力就算了。。
我们直接考虑怎样优化：
我们考虑到可以先按x排序，然后分治，先分别求解两个子问题。
假设我们已经求得了两个子问题的答案。
那么如果合并时，答案能够更新，当且仅当两个子区间中存在更近的点对。
那么分别枚举两个子区间的点？？ 还不是和n2一样T掉。。
实际上，有很多点是没必要枚举的。
因为我们已经得到了两个子区间的答案，
那么如果存在更小的答案，可能的区间也仅仅只在[x[Mid]-min (ans1, ans2), x[mid]+min (ans1, ans2)];
所以呢，这要在这个区间中暴力枚举更新就好了。。
这样的话，限制稍微宽松一些，但肯定可以保证不会漏掉答案。。一般没人无聊到去卡掉这个
#include <algorithm> #include <iostream> #include <cstdio> #include <cmath> using namespace std; int n; double Mx; struct Point { double x,y; bool operator < (Point &a) { return x<a.x || (x==a.x && y<a.y); } }d[200010]; inline double Calc (int a, int b) { return sqrt (fabs (d[a].x-d[b].x)*fabs (d[a].x-d[b].x)+fabs (d[a].y-d[b].y)*fabs (d[a].y-d[b].y)); } int search (int l, int r, double val) { int Mid; while (l<r) { Mid= (l+r) >> 1; if (d[Mid].x>=val) r=Mid; else l=Mid+1; } return r; } double Solve (int l, int r) { if (l==r) return 2147483647; double Ans; int Mid= (l+r) >> 1,Lp,Rp; Ans=min (Solve (l, Mid), Solve (Mid+1, r)); Lp=search (l, Mid, d[Mid].x-Ans), Rp=search (Mid+1, r, d[Mid+1].x+Ans); for (int i=Lp;i<=Mid;++i) for (int j=Mid+1;j<=Rp;++j) Ans=min (Ans, Calc (i, j)); return Ans; } int main () { std::ios::sync_with_stdio (false); cin >> n; for (int i=1;i<=n;++i) cin >> d[i].x >> d[i].y; sort (d+1, d+n+1); printf ("%.4lf\n", Solve (1, n)); return 0; }
原文：https://www.cnblogs.com/Bhllx/p/9823309.html