Pagini recente » Cod sursa (job #1148661) | Cod sursa (job #3209319) | Cod sursa (job #2641882) | Cod sursa (job #2257099) | Cod sursa (job #2668375)
#include <bits/stdc++.h>
using namespace std;
struct Punct
{
double x,y;
} v[100005],v1[100005],v2[100005];
int64_t n;
int64_t Distanta(const Punct a,const Punct b)
{
return (a.x-b.x)*(a.x-b.x)+(b.y-a.y)*(b.y-a.y);
}
bool Compare(const Punct &a,const Punct &b)
{
return a.y<b.y;
}
bool Compare1(const Punct &a,const Punct &b)
{
return a.x<b.y;
}
int64_t Fct(int st,int dr)
{
if(dr-st<=1)
return 4e18;
else if(dr-st==2)
{
if(v1[st].y>v1[st+1].y)
swap(v1[st],v1[st+1]);
return Distanta(v1[st],v1[st+1]);
}
else
{
int mi=(st+dr)>>1;
int64_t mn=min(Fct(st,mi),Fct(mi,dr));
sort(v1+st,v1+dr,Compare);
int64_t h=0;
for(int i=st; i<dr; i++)
if(abs(v1[i].x-v[mi].x)<=mn)
v2[++h]=v1[i];
for(int i=0; i<h-1; i++)
for(int j=i+1; j<h&&j-i<8; j++)
mn=min(mn,Distanta(v2[i],v2[j]));
return mn;
}
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
f>>n;
for(int i=0; i<n; i++)
f>>v[i].x>>v[i].y,v1[i]=v[i];
sort(v,v+n,Compare1);
g<<fixed<<setprecision(6)<<sqrt(Fct(1,n));
return 0;
}