题解 | #小红的星屑共鸣#

最开始完全没有思路，后面搜了一下才知道用分治法做，然后去学分治法，学了感觉有点像快排，但是和快排不一样的是，要考虑中间情况（就是两个点跨中线的情况），这是个超级大坑。

• 中间的可能的点，必须要先用y排序一次，这样筛选的时候可以用y，这样两层循环的时候，y的差值的平方大于当前得到的最短距离，就可以break，不然时间复杂度要超。而且第二层循环j不能0开始，要从i开始，从0开始会导致第一个点j=0和当前点距离过大，直接跳出循环，当前点后面的都没法计算了。

• 关于y的排序，这里可以每个递归都排序一次，也可以用归并排序，归并排序的时间复杂度要低一点，，但是要用全局变量，我第一次在递归里面写归并排序，最开始也不会写，也是让ai给了思路才写出来。

debug到最后脑子都晕了，实在看不动了，让ai帮我debug了一下，找出来了上面两个坑，最后也勉强算是写出来了，代码有点丑陋，大家将就看看。

#include <climits>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


struct Point {
    long long x;
    long long y;
};

vector<Point> sortByY;
vector<Point> tempForChange;


bool lessRow(Point& a, Point& b) {
    if (a.x < b.x) return true;  // 综合 x,y 升序排序
    return false;
}


long long dist2(Point& a, Point& b) {
    long long distance = (a.x - b.x) * (a.x - b.x)
                         + (a.y - b.y) * (a.y - b.y);
    return distance;
}


long long solve(vector<Point>& datas, int L, int R) {
    int n = datas.size();
    if (R == L) {
        sortByY[L] = datas[L];
        return LLONG_MAX;
    }
    if (R - L == 1) {
        long long distance = dist2(datas[L], datas[R]);
        if (datas[R].y > datas[L].y) {
            sortByY[L] = datas[L];
            sortByY[R] = datas[R];
        } else {
            sortByY[L] = datas[R];
            sortByY[R] = datas[L];
        }
        return distance;
    }
    // 处理中间情况
    long long Ldist = solve(datas, L, (L + R) / 2);
    long long Rdist = solve(datas, (L + R) / 2 + 1, R);

    // 归并排序
    int l = L;
    int indMid = (L + R) / 2;
    int r = indMid + 1;
    int start = l;
    while (l <= indMid && r <= R) {
        if (sortByY[l].y <= sortByY[r].y) {
            tempForChange[start++] = sortByY[l];
            l++;
        }
        else {
            tempForChange[start++] = sortByY[r];
            r++;
        }
    }

    while (l <= indMid) {
        tempForChange[start++] = sortByY[l];
        l++;
    }

    while (r <= R) {
        tempForChange[start++] = sortByY[r];
        r++;
    }

    for (int i = L; i < R + 1; i++) {
        sortByY[i] = tempForChange[i];
    }

    long long curDist = min(Ldist, Rdist);
    Point mid = datas[(L + R) / 2];

    vector<Point> midsPoint;

    // 扫描 sortByY
    for (int i = L; i < R + 1; i++) {
        if ((sortByY[i].x - mid.x) * (sortByY[i].x - mid.x) < curDist)
            midsPoint.push_back(sortByY[i]);
    }


    for (int i = 0; i < midsPoint.size(); i++) {
        for (int j = i + 1; j < midsPoint.size(); j++) {
            long long tempDist = LLONG_MAX;
            // 控制y的距离
            if ((midsPoint[i].y - midsPoint[j].y) * (midsPoint[i].y - midsPoint[j].y) >
                    curDist) break;
            curDist = min(curDist, dist2(midsPoint[i], midsPoint[j]));
        }
    }

    return curDist;
}


int main() {
    int n;
    cin >> n;

    sortByY.resize(n);
    tempForChange.resize(n);

    vector<Point> datas;
    Point p;
    for (int i = 0; i < n; ++i) {
        cin >> p.x >> p.y;
        datas.push_back(p);
    }

    sort(datas.begin(), datas.end(), lessRow);

    long long distance;

    distance = solve(datas, 0, n - 1);

    cout << distance;

    return 0;
}