题目描述
给定平面上N个点，找出其中的一对点的距离，使得在这N个点的所有点的对中，该距离为所有点对中最小的。（2<=n<50000）
输入格式
输入第一行一个整数N，表示点的个数，以下N行，每行二个实数，表示一个点的横坐标和纵坐标
输出格式
一个数，最小点对的距离。
(输出保留两位小数)
样例
Input 1
3
1 1
1 2
2 2
Output 1
1.00
样例解释
对于输入样例中的点，(1, 1)和(1, 2)之间的距离是 1，(1, 2)和(2, 2)之间的距离是1，(1, 1)和(2, 2)之间的距离是sqrt(2)，所以最小的点对距离是1
数据范围
2<=n<50000
WA20:
#include<bits/stdc++.h>
using namespace std;
int n,tt[50010];
typedef struct node{
double x,y;
}node;
node a[50010];
bool cmp(node fi,node se){
if(fi.x==se.x)return (fi.y<se.y);
else return (fi.x<se.x);
}
bool cmp2(int fi,int se){
return a[fi].y<a[se].y;
}
double dis(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double solve(int l,int r){
if(l==r)return 0x3f;
if(r-l==1)return dis(a[l].x,a[l].y,a[r].x,a[r].y);
double ans=0;
int mid=(l+r)/2,k=0;
double ans1=solve(l,mid),ans2=solve(mid,r);
ans=min(ans1,ans2);
for(int i=l;i<=r;i++){
if(fabs(a[mid].x-a[i].x)<ans)tt[k++]=i;
}
sort(tt,tt+k,cmp2);
for(int i=0;i<k;i++){
for(int j=i+1;j<k&&a[tt[j]].y-a[tt[i]].y<ans;j++){
double now=dis(a[tt[i]].x,a[tt[i]].y,a[tt[j]].x,a[tt[j]].y);
ans=min(now,ans);
}
}
return ans;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a,a+n,cmp);
printf("%.2lf",solve(0,n-1));
return 0;
}