洛谷-【模板】1429 平面最近点对（加强版）

题目描述
给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的
输入格式
第一行：n；2≤n≤200000
接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。
输出格式
仅一行，一个实数，表示最短距离，精确到小数点后面4位。

输入输出样例
输入 #1
3
1 1
1 2
2 2

输出 #1
1.0000

说明/提示
0<=x,y<=10^9

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1000001;
const int INF = 2 << 20;
int n, temp[maxn];
struct Point {
    double x, y;
}S[maxn];
bool cmp(const Point &a, const Point &b){
    if (a.x == b.x) return a.y < b.y;
    else return a.x < b.x;
}
bool cmps(const int &a, const int &b) { return S[a].y < S[b].y; }
double min(double a, double b) { return a < b ? a : b; }
double dist(int i, int j) {
    double x = (S[i].x - S[j].x) * (S[i].x - S[j].x);
    double y = (S[i].y - S[j].y) * (S[i].y - S[j].y);
    return sqrt(x + y);
}
double merge(int left, int right){
    double d = INF;
    if (left == right)
        return d;
    if (left + 1 == right)
        return dist(left, right);
    int mid = (left + right) >> 1;
    double d1 = merge(left, mid);
    double d2 = merge(mid + 1, right);
    d = min(d1, d2);
    int i, j, k = 0;
    for (i = left; i <= right; i++)
        if(fabs(S[mid].x - S[i].x) < d) temp[k++] = i;
    sort(temp, temp + k, cmps);
    for (i = 0; i < k; i++)
        for (j = i + 1; j < k && S[temp[j]].y - S[temp[i]].y < d; j++) d=min(d,dist(temp[i], temp[j]));
    return d;
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lf%lf", &S[i].x, &S[i].y);
    sort(S, S + n, cmp);
    return !printf("%.4lf\n", merge(0, n - 1));
}