暂鸽

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 100010
using namespace std;
void chkmin(double x,double y) {if (x>y) x=y;}
int n;
struct point
{
double x,y;
point(){};
point(double _x,double _y)
{
x=_x,y=_y;
}
point operator - (const point &b) const
{
return point(x-b.x,y-b.y);
}
double norm()const
{
return sqrt(x*x+y*y);
}
bool operator < (const point &a) const
{
return x<a.x;
}
}p[N];
double solve(int l,int r)
{
if (l+1==r) return 1e20;
int mid=l+r>>1;
double x0=(p[mid-1].x+p[mid].x)/2.0;
double d=min(solve(l,mid),solve(mid,r));
static point a[N],b[N],c[N];
int b_n=0,c_n=0;
int L=l,R=mid;
for (int i=l;i<r;i++)
{
if (L<mid && (R==r || p[L].y<p[R].y))
{
a[i]=p[L++];
if (x0-d<a[i].x) b[b_n++]=a[i];
}
else
{
a[i]=p[R++];
if (a[i].x<x0+d) c[c_n++]=a[i];
}
}
for (int i=l;i<r;i++) p[i]=a[i];
for (int i=0,j=0;i<b_n || j<c_n;)
{
if (i<b_n && (j==c_n || b[i].y<c[j].y))
{
for (int k=j-1;k>=0;k--)
{
if (b[i].y-d>=c[k].y) break;
d=min(d,(c[k]-b[i]).norm());
}
i++;
}
else
{
for (int k=i-1;k>=0;k--)
{
if (c[j].y-d>=b[k].y) break;
d=min(d,(b[k]-c[j]).norm());
}
j++;
}
}
return d;
}
int main()
{
while (scanf("%d",&n),n)
{
for (int i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p,p+n);
printf("%.2f\n",solve(0,n)/2.0);
}
return 0;
}
05-22 02:29
查看更多