题解 | 小红的星屑共鸣

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

struct Point {
    ll x, y;
};

// 计算两点距离的平方
ll dist2(const Point& a, const Point& b) {
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return dx * dx + dy * dy;
}

// 按 y 坐标归并排序两个已排序的区间 [l, mid] 和 [mid+1, r]
void mergeByY(vector<Point>& pts, int l, int mid, int r) {
    vector<Point> temp(r - l + 1);
    int i = l, j = mid + 1, k = 0;
    
    // 合并两个有序序列
    while (i <= mid && j <= r) {
        if (pts[i].y <= pts[j].y) {
            temp[k++] = pts[i++];
        } else {
            temp[k++] = pts[j++];
        }
    }
    
    // 处理剩余元素
    while (i <= mid) temp[k++] = pts[i++];
    while (j <= r) temp[k++] = pts[j++];
    
    // 复制回原数组
    for (int idx = 0; idx < (int)temp.size(); idx++) {
        pts[l + idx] = temp[idx];
    }
}

// 分治求解最近点对距离平方
ll closestPair(vector<Point>& pts, int l, int r) {
    // 递归终止：区间内点数 <= 3，直接暴力求解
    if (r - l <= 2) {
        ll minDist = LLONG_MAX;
        for (int i = l; i <= r; i++) {
            for (int j = i + 1; j <= r; j++) {
                minDist = min(minDist, dist2(pts[i], pts[j]));
            }
        }
        // 按 y 排序这个小段，为上层归并做准备
        sort(pts.begin() + l, pts.begin() + r + 1, 
             [](const Point& a, const Point& b) { return a.y < b.y; });
        return minDist;
    }
    
    // 分治
    int mid = (l + r) / 2;
    ll midX = pts[mid].x;
    
    // 递归求解左右两半
    ll leftMin = closestPair(pts, l, mid);
    ll rightMin = closestPair(pts, mid + 1, r);
    ll minDist = min(leftMin, rightMin);
    
    // 归并：将左右两半按 y 合并，使 [l, r] 按 y 有序
    mergeByY(pts, l, mid, r);
    
    /*如果 x 差平方已经比当前最优距离平方还大，
      那就算 y 差为 0，整个距离也 ≥ 这个值，
      不可能更新最优解 → 直接不加入 strip */
    vector<Point> strip;
    for (int i = l; i <= r; i++) {
        ll dx = pts[i].x - midX;
        if (dx * dx < minDist) {
            strip.push_back(pts[i]);
        }
    }
    
    // 检查中缝带内的点对（strip 已按 y 有序）
    for (int i = 0; i < (int)strip.size(); i++) {
        for (int j = i + 1; j < (int)strip.size(); j++) {
            //同上，y差方大则不用比了
            ll dy = strip[j].y - strip[i].y;
            if (dy * dy >= minDist) break;
           
            minDist = min(minDist, dist2(strip[i], strip[j]));
        }
    }
    
    return minDist;
}

int main() {
    int n;
    cin >> n;
    
    vector<Point> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y;
    }
    
    // 按 x 坐标排序
    sort(pts.begin(), pts.end(), 
         [](const Point& a, const Point& b) { return a.x < b.x; });
    
    // 求解并输出
    cout << closestPair(pts, 0, n - 1) << "\n";
    
    return 0;
}