一道非常经典的分治题目
首先先把所有点按 \(x\) 坐标排个序，方便分治。
每次将查询区间一分为二，分治出两个区间的答案。
那么合并的时候就只会有下面三种情况
- 答案在左区间
- 答案在右区间
- 答案由左区间和右区间各一个点组成
我们可以先把右区间那些 \(x\) 坐标减去左区间里最大的 \(x\) 坐标 < min{左区间答案,右区间答案}的都筛出来，因为这些点是有可能对新答案产生贡献的。
然后枚举下左边的点与右边的点更新答案，然而这样子明显 GG
要快速的找出那些对于某个左边点可能有贡献的右边点，方法就是在分治的过程中把每个区间的点都按 \(y\) 坐标排序
不难求证，对于每个点可能有贡献的最多只会有 \(6\) 个点，所以复杂度就有了保障 \((N·log_2N)\)
#include#include #include #include #define sqr(x) ((x) * (x))const int MaxN = 2e5 + 5;const int Inf = 0x3f3f3f3f;int N;struct Node{ double x, y;}A[MaxN], C[MaxN];bool comp(Node a, Node b){ return a.x < b.x;}inline double dist(double X1, double Y1, double X2, double Y2){ return sqrt(sqr(X1 - X2) + sqr(Y1 - Y2)); }double DAC(int l, int r){ if(l == r) return Inf; int tot = 0, p = 1, mid = l + r >> 1; double t = A[mid].x, d = std::min(DAC(l, mid), DAC(mid + 1, r)); for(int i = mid + 1; i <= r; ++i) if(A[i].x - t < d) C[++tot] = A[i]; for(int i = l; i <= mid; ++i) { if(t - A[i].x >= d) continue; while(p <= tot && A[i].y - C[p].y >= d) ++p; for(int j = p; j <= tot && C[p].y - A[i].y < d; ++j) d = std::min(d, dist(A[i].x, A[i].y, C[j].x, C[j].y)); } for(int i = l, l1 = l, l2 = mid + 1; i <= r; ++i) { if((A[l1].y < A[l2].y && l1 <= mid) || l2 > r) C[i] = A[l1++]; else C[i] = A[l2++]; } for(int i = l; i <= r; ++i) A[i] = C[i]; return d;}int main(){ scanf("%d", &N); for(int i = 1; i <= N; ++i) scanf("%lf %lf", &A[i].x, &A[i].y); std::sort(&A[1], &A[N + 1], comp); printf("%.4lf\n", DAC(1, N)); return 0;}