存个模板:
是用分治写的时间复杂度 nlogn
但是本题好像还有一种玄学做题法:

我们充分发扬人类智慧:

将所有点全部绕原点旋转同一个角度,然后按x坐标排序

根据数学直觉,在随机旋转后,答案中的两个点在数组中肯定不会离得太远

所以我们只取每个点向后的5个点来计算答案

这样速度快得飞起,在n=1000000时都可以在1s内卡过。。。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=200100;
const double eps=1e-8;
const double dnf=1e20;
struct Point
{
    double x,y;
    void input(void)
    {
        scanf("%lf%lf",&x,&y);
    }
};
double dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

Point p[maxn];
Point temp[maxn];

bool cmpx(const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}

bool cmpy(const Point &a,const Point &b)
{
    return a.y<b.y||(a.y==b.y&&a.x<b.x);
}

double closest_pair(int l,int r)
{
    double d=dnf;
    if(l==r) return d;
    if(l+1==r) return dis(p[l],p[r]);
    int mid=(l+r)/2;
    double d1=closest_pair(l,mid);
    double d2=closest_pair(mid+1,r);
    d=min(d1,d2);
    int cnt=0;
    for(int i=l;i<=r;i++)
    {
        if(abs(p[mid].x-p[i].x)<=d)
            temp[cnt++]=p[i];
    }
    sort(temp,temp+cnt,cmpy);
    for(int i=0;i<cnt;i++)
        for(int j=i+1;j<cnt&&temp[j].y-temp[i].y<d;j++)
            d=min(d,dis(temp[i],temp[j]));
    return d;
}

int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        p[i].input();
    sort(p+1,p+1+n,cmpx);
    printf("%.4f\n",closest_pair(1,n));
    return 0;
}