秋水1024 @ 2021-07-26 20:37:12
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,s[100086],tot;
struct node{
double x,y;
}e[200021];
bool cmp(node a,node b){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
bool cmp1(int a,int b){
return e[a].y<e[b].y;
}
double jl(int a,int b){
double jl0=(e[a].x-e[b].x)*(e[a].x-e[b].x)+(e[a].y-e[b].y)*(e[a].y-e[b].y);
return sqrt(jl0);
}
double merge(int l,int r){
if(l==r)return double(2<<20)+0.1;
if(l==r-1)return jl(l,r);
int mid=(l+r)/2;
double d=min(merge(l,mid),merge(mid+1,r));
memset(s,0,sizeof(s));s[1]=mid;tot=1;
for(int i=l;i<=r;i++)
if(abs(e[mid].x-e[i].x)<=d)
s[++tot]=i;
sort(s+1,s+tot+1,cmp1);
for(int i=1;i<=tot;i++)
for(int j=i+1;j<=tot&&abs(e[j].y-e[i].y)<=d;j++){
double d0=jl(i,j);
if(d>d0)d=d0;
}
// cout<<l<<" "<<r<<" "<<d<<endl;
return d;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)scanf("%lf%lf",&e[i].x,&e[i].y);
//cout<<e[1].x<<e[1].y<<e[2].x<<e[2].y;
sort(e,e+n+1, cmp);
double ans=merge(1, n);
printf("%.4lf\n",ans);
return 0;
}
by 秋水1024 @ 2021-07-26 20:37:44
大红大紫的
我傻了555
by seh_sjij @ 2021-09-29 08:50:40
sort(e,e+n+1, cmp);
应为
sort(e+1,e+n+1, cmp);