Pagini recente » Cod sursa (job #3221257) | Cod sursa (job #2609020) | Cod sursa (job #1195478) | Cod sursa (job #2855346) | Cod sursa (job #432477)
Cod sursa(job #432477)
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define Nmax 100005
#define ll long long
const ll inf = 100000000000000000LL;
struct pct
{
int x,y;
} v[Nmax],a[Nmax];
struct cmp
{
inline bool operator()(pct i,pct j)
{
if (i.x == j.x)
return (i.y < j.y);
return (i.x < j.x);
}
};
struct cmp2
{
inline bool operator()(pct i,pct j)
{
return (i.y < j.y);
}
};
int N;
double dist(pct i,pct j)
{
return (sqrt( (i.x-j.x)*(i.x-j.x) + (i.y-j.y)*(i.y-j.y) ) );
}
double tractor(int st,int dr)
{
double opt=inf;
for(int i=st;i<dr;++i)
for(int j=i+1;j<=dr;++j)
if (opt > dist(v[i],v[j]))
opt = dist(v[i],v[j]);
return opt;
}
int caut(pct x,double Dmin,int M)
{
int st=1,dr=M,last=M,mid;
for(; st<=dr ;)
{
mid = st + (dr-st)/2;
if (x.y-Dmin <= a[mid].y)
{
dr=mid-1;
last = mid;
}
else
st = mid+1;
}
return last;
}
double calc(int st,int dr)
{
int mid,M=0;
double d,Min;
if (st>dr)
return inf;
if (dr-st < 4)
return tractor(st,dr);
mid = st + (dr-st)/2;
d = min ( calc(st,mid) ,calc(mid+1,dr) );
Min = d;
for(int i=mid+1; v[i].x <= v[mid].x+d && i<=dr;++i)
a[++M]=v[i];
sort(a+1,a+M+1,cmp2());
for(int i=st;i<=mid;++i)
for(int j=caut(v[i],d,M); j<=M && v[i].y-d<=a[j].y && a[j].y<=v[i].y+d ;++j)
if (Min > dist(v[i],a[j]))
Min = dist(v[i],a[j]);
return Min;
}
void cit()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&N);
for(int i=1;i<=N;++i)
scanf("%d%d",&v[i].x,&v[i].y);
}
int main()
{
cit();
sort(v+1,v+N+1,cmp());
printf("%.6lf\n",calc(1,N));
return 0;
}