转载请注明出处：http://blog.csdn.net/vmurder/article/details/42913023
题解：很经典的分治计算几何模型。
我们对点的x坐标排序，然后进行分治，同时分治完了还需要求两边的互相影响。
一、在左边取两个点，右边一个。
二、在右边取两个点，左边一个。
这个时候我们可以对左右两边的点再分别按照y值排序，
当然，因为已经出来了一个比较优的ans，所以当一个点距离两边中界过远，那么我们就把它扔掉再不用管了。
还有就是两边的点，y坐标距离过大的也不能进行选择，所以又进行一次剪枝。
然后就是暴力枚举，但是每个点在左边/右边选择的那两个点是有范围的（就是上述剪枝）。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 201000
#define inf 1e15
using namespace std;
struct Point
{
double x,y;
bool operator < (const Point &a)const{return x<a.x;}
void read(){scanf("%lf%lf",&x,&y);}
}p[N],L[N],R[N];
inline bool cmp(const Point &a,const Point &b){return a.y<b.y;}
inline double Calc(Point &a,Point &b,Point &c){return
sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))+
sqrt((a.x-c.x)*(a.x-c.x)+(a.y-c.y)*(a.y-c.y))+
sqrt((b.x-c.x)*(b.x-c.x)+(b.y-c.y)*(b.y-c.y));
}
int n;
double ans=inf;
void solve(int l,int r)
{
int i,j,k;
if(r-l<=20)
{
for(i=l;i<=r;i++)
for(j=i+1;j<=r;j++)
for(k=j+1;k<=r;k++)
ans=min(ans,Calc(p[i],p[j],p[k]));
return ;
}
int mid=l+r>>1;
solve(l,mid),solve(mid+1,r);
// 处理两段区间中间的影响
double x=(p[mid].x+p[mid+1].x)/2;
int ltop=0,rtop=0;
for(i=mid ;i &&x-p[i].x<ans/2;i--)L[++ltop]=p[i];
for(i=mid+1;i<=r&&p[i].x-x<ans/2;i++)R[++rtop]=p[i];
sort(L+1,L+ltop+1,cmp);
sort(R+1,R+rtop+1,cmp);
int top=1,tail=1;
for(i=1;i<=ltop;i++) // 左边一个点，右边两个点
{
while(L[i].y-R[top].y >ans/2&&top <rtop)++top;
while(R[tail].y-L[i].y<ans/2&&tail<rtop)++tail;
for(j=top;j<=tail;j++)
for(k=j+1;k<=tail;k++)
ans=min(ans,Calc(L[i],R[j],R[k]));
}
top=tail=1;
for(i=1;i<=rtop;i++) // 右边一个点，左边两个点
{
while(R[i].y-L[top].y >ans/2&&top<ltop)++top;
while(L[tail].y-R[i].y<ans/2&&tail <ltop)++tail;
for(j=top;j<=tail;j++)
for(k=j+1;k<=tail;k++)
ans=min(ans,Calc(R[i],L[j],L[k]));
}
}
int main()
{
// freopen("test.in","r",stdin);
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)p[i].read();
sort(p+1,p+n+1);
solve(1,n);
printf("%.6lf\n",ans);
return 0;
}