解题思路

核心做法（分治 + 归并按 y 排序）：

1. 先按 x 坐标排序所有点。
2. 递归把点集分成左右两半，分别求出左右内部的最小距离平方 d。
3. 在合并阶段，把当前区间按 y 坐标归并排序（保证递归返回后区间内点按 y 有序）。
4. 只需检查“中线附近”宽度为 sqrt(d) 的条带（strip）：满足 (x-midx)^2 < d 的点。
5. 条带内点按 y 有序后，对每个点只需向后检查 y 差平方小于 d 的少量点（理论保证常数个），更新最小值。

最终得到全局最小距离平方。

复杂度分析

• 时间复杂度：O(n log n)（每层分治做一次线性归并与条带检查，总层数 log n）
• 空间复杂度：O(n)（辅助数组用于归并）

代码实现

Python

import sys

def closest_pair(points):
    # points: 已按 x 排序的点列表 [(x,y), ...]
    n = len(points)
    tmp = [None] * n  # 归并时的临时数组

    def solve(l, r):
        # 计算 points[l:r] 的最近距离平方，并保证 points[l:r] 按 y 排序
        if r - l <= 3:
            # 小规模直接暴力
            best = 1 << 62
            for i in range(l, r):
                x1, y1 = points[i]
                for j in range(i + 1, r):
                    x2, y2 = points[j]
                    dx = x1 - x2
                    dy = y1 - y2
                    d = dx * dx + dy * dy
                    if d < best:
                        best = d
            # 按 y 排序，方便上层归并
            points[l:r] = sorted(points[l:r], key=lambda p: p[1])
            return best

        m = (l + r) // 2
        midx = points[m][0]
        d = solve(l, m)
        dr = solve(m, r)
        if dr < d:
            d = dr

        # 归并：把两段按 y 有序的数组合并
        i, j, k = l, m, l
        while i < m and j < r:
            if points[i][1] <= points[j][1]:
                tmp[k] = points[i]
                i += 1
            else:
                tmp[k] = points[j]
                j += 1
            k += 1
        while i < m:
            tmp[k] = points[i]
            i += 1
            k += 1
        while j < r:
            tmp[k] = points[j]
            j += 1
            k += 1
        points[l:r] = tmp[l:r]

        # 收集条带点：只取 (x-midx)^2 < d 的点
        strip = []
        for t in range(l, r):
            dx = points[t][0] - midx
            if dx * dx < d:
                strip.append(points[t])

        # 条带按 y 已有序，只需检查后面 y 距离足够近的点
        s = len(strip)
        for a in range(s):
            x1, y1 = strip[a]
            b = a + 1
            while b < s:
                dy = strip[b][1] - y1
                if dy * dy >= d:
                    break
                dx = strip[b][0] - x1
                dist = dx * dx + dy * dy
                if dist < d:
                    d = dist
                b += 1
        return d

    points.sort()  # 按 x 排序
    return solve(0, n)

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    points = []
    idx = 1
    for _ in range(n):
        x = int(data[idx]); y = int(data[idx + 1])
        idx += 2
        points.append((x, y))
    print(closest_pair(points))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    static class Point {
        int x, y;
        Point(int x, int y) { this.x = x; this.y = y; }
    }

    // 按 x 排序的点数组
    static Point[] pts;
    // 归并按 y 的临时数组
    static Point[] tmp;

    // 读入指针
    static int p = 0;

    // 简单快读：从字节数组里读一个整数（默认输入合法）
    static int nextInt(byte[] a) {
        while (p < a.length && a[p] <= ' ') p++;
        int sign = 1;
        if (a[p] == '-') { sign = -1; p++; }
        int v = 0;
        while (p < a.length && a[p] > ' ') {
            v = v * 10 + (a[p] - '0');
            p++;
        }
        return v * sign;
    }

    static long closestPair(Point[] points) {
        pts = points;
        // 按 x 排序（若 x 相同按 y 排）
        Arrays.sort(pts, (a, b) -> a.x != b.x ? a.x - b.x : a.y - b.y);
        tmp = new Point[pts.length];
        return solve(0, pts.length);
    }

    // 计算 pts[l:r) 的最近距离平方，并保证 pts[l:r) 按 y 排序
    static long solve(int l, int r) {
        if (r - l <= 3) {
            // 小范围直接暴力
            long best = Long.MAX_VALUE;
            for (int i = l; i < r; i++) {
                for (int j = i + 1; j < r; j++) {
                    long dx = (long) pts[i].x - pts[j].x;
                    long dy = (long) pts[i].y - pts[j].y;
                    long d = dx * dx + dy * dy;
                    if (d < best) best = d;
                }
            }
            // 小段按 y 排序，方便上层合并
            Arrays.sort(pts, l, r, Comparator.comparingInt(o -> o.y));
            return best;
        }

        int m = (l + r) >>> 1;
        int midx = pts[m].x;

        // 分治求左右最小值
        long d = solve(l, m);
        long dr = solve(m, r);
        if (dr < d) d = dr;

        // 归并：两段按 y 有序合并
        int i = l, j = m, k = l;
        while (i < m && j < r) {
            if (pts[i].y <= pts[j].y) tmp[k++] = pts[i++];
            else tmp[k++] = pts[j++];
        }
        while (i < m) tmp[k++] = pts[i++];
        while (j < r) tmp[k++] = pts[j++];
        for (int t = l; t < r; t++) pts[t] = tmp[t];

        // 收集条带点：只保留 (x-midx)^2 < d 的点（此时按 y 已有序）
        Point[] strip = new Point[r - l];
        int s = 0;
        for (int t = l; t < r; t++) {
            long dx = (long) pts[t].x - midx;
            if (dx * dx < d) strip[s++] = pts[t];
        }

        // 条带检查：只看 y 距离平方 < d 的少量后续点
        for (int a = 0; a < s; a++) {
            for (int b = a + 1; b < s; b++) {
                long dy = (long) strip[b].y - strip[a].y;
                if (dy * dy >= d) break;
                long dx = (long) strip[b].x - strip[a].x;
                long dist = dx * dx + dy * dy;
                if (dist < d) d = dist;
            }
        }
        return d;
    }

    public static void main(String[] args) throws Exception {
        // 读取全部输入（n 最大 1e5，这样读很快）
        byte[] a = System.in.readAllBytes();
        p = 0;

        int n = nextInt(a);
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            int x = nextInt(a);
            int y = nextInt(a);
            points[i] = new Point(x, y);
        }

        long ans = closestPair(points);
        System.out.print(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y;
};

static vector<Point> pts;
static vector<Point> tmp;

// 计算 pts[l:r) 的最近距离平方，并保证 pts[l:r) 按 y 排序
long long solve(int l, int r) {
    if (r - l <= 3) {
        long long best = (1LL << 62);
        for (int i = l; i < r; i++) {
            for (int j = i + 1; j < r; j++) {
                long long dx = 1LL * pts[i].x - pts[j].x;
                long long dy = 1LL * pts[i].y - pts[j].y;
                long long d = dx * dx + dy * dy;
                if (d < best) best = d;
            }
        }
        sort(pts.begin() + l, pts.begin() + r, [](const Point& a, const Point& b){
            return a.y < b.y;
        });
        return best;
    }

    int m = (l + r) / 2;
    int midx = pts[m].x;
    long long d = solve(l, m);
    long long dr = solve(m, r);
    if (dr < d) d = dr;

    // 归并按 y
    int i = l, j = m, k = l;
    while (i < m && j < r) {
        if (pts[i].y <= pts[j].y) tmp[k++] = pts[i++];
        else tmp[k++] = pts[j++];
    }
    while (i < m) tmp[k++] = pts[i++];
    while (j < r) tmp[k++] = pts[j++];
    for (int t = l; t < r; t++) pts[t] = tmp[t];

    // 条带点（按 y 已有序）
    vector<Point> strip;
    strip.reserve(r - l);
    for (int t = l; t < r; t++) {
        long long dx = 1LL * pts[t].x - midx;
        if (dx * dx < d) strip.push_back(pts[t]);
    }

    // 检查后续 y 足够近的点
    for (int a = 0; a < (int)strip.size(); a++) {
        for (int b = a + 1; b < (int)strip.size(); b++) {
            long long dy = 1LL * strip[b].y - strip[a].y;
            if (dy * dy >= d) break;
            long long dx = 1LL * strip[b].x - strip[a].x;
            long long dist = dx * dx + dy * dy;
            if (dist < d) d = dist;
        }
    }
    return d;
}

long long closest_pair(vector<Point>& points) {
    pts = points;
    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b){
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    tmp.assign(pts.size(), Point{0, 0});
    return solve(0, (int)pts.size());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }
    cout << closest_pair(points) << "\n";
    return 0;
}

题目内容

某城市计划在多个地点建立信号塔，所有信号塔的覆盖范围均为圆形，现给定所有信号塔的坐标(二维平面上的点)，要求检测信号塔间的距离 $(x_1-x_2 )^2+(y_1- y_2)^2$，请返回所有信号塔间的最小距离。

输入描述

第一行为整数 $n(2≤n≤100000)$，表示表示信号塔数量。

接下来 $n$ 行，每行包含两个整数 $x(-100000≤x≤100000)$ 和 $y(-100000≤y≤100000)$，以空格分隔，表示信号塔的坐标。

输出描述

一个整数，表示所有信号塔间的最小距离。

样例1

输入

5
0 0
0 5
3 4
3 5
3 6

输出

1

说明

最近的点对是 $(3,4)$ 和 $(3,5)$，距离为 $(3-3)^2+(5-4)^2=1$ 。

样例2

输入

4
0 0
0 1
1 0
1 1

输出

1

说明

最近的点对是 $(0,0)、(0,1)$ 和 $(0,0)、(1,0)$，距离为 $(0-0)^2+ (1-0)^2=1$

样例3

输入

2
0 0
1 1

输出

2

说明

最近的两个点是 $(0,0)$ 和 $(1,1)$，距离为 $(1-0)^2+(1-0)^2=2$ 。