Rt,是有什么没有在第一次跑的时候先处理好吗?
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node
{
double x;
double y;
}arr[200005],brr[200005];
bool cmp(int a,int b)
{
return arr[a].y<arr[b].y;
}
int temp[200005];
double dis(Node a,Node b)
{
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
double quick_sort(int l,int r)
{
if(l>=r)
{
return 2e9;
}
int mid=l+r>>1;
double d=min(quick_sort(l,mid),quick_sort(mid+1,r));
int p1=l,p2=mid+1,k=l;
while(p1<=mid && p2<=r)
{
if(arr[p1].x<arr[p2].x)
{
brr[k]=arr[p1];
p1++;
}else
{
brr[k]=arr[p2];
p2++;
}
k++;
}
while(p1<=mid)
{
brr[k]=arr[p1];
k++;
p1++;
}
while(p2<=r)
{
brr[k]=arr[p2];
k++;
p2++;
}
for(int i=l;i<=r;i++)
{
arr[i]=brr[i];
}
temp[0]=0;
for(int i=l;i<=r;i++)
{
if(fabs(arr[mid].x-arr[i].x)<d)
{
temp[0]++;
temp[temp[0]]=i;
}
}
sort(temp+1,temp+temp[0]+1,cmp);
for(int i=1;i<=temp[0];i++)
{
for(int j=i+1;j<=temp[0] && arr[temp[j]].y-arr[temp[i]].y<d;j++)
{
d=min(d,dis(arr[temp[i]],arr[temp[j]]));
}
}
return d;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>arr[i].x>>arr[i].y;
}
quick_sort(1,n);
printf("%.4lf",quick_sort(1,n));
return 0;
}