Pagini recente » Cod sursa (job #3210796) | Cod sursa (job #411655)
Cod sursa(job #411655)
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long
#define INF 1LL<<60
#define NMAX 100005
#define x first
#define y second
typedef pair <int,int> p;
p a[NMAX];
int n,i;
inline ll dst(int i,int j)
{
return 1LL*(a[i].x-a[j].x)*(a[i].x-a[j].x)+
1LL*(a[i].y-a[j].y)*(a[i].y-a[j].y);
}
inline bool cmp(const p &a,const p &b)
{
return a.x<b.x||a.x==b.x&&a.y<b.y;
}
ll solve(int st,int dr)
{
ll Min=INF,Min1;
long double MIN;
int mj=(st+dr)>>1;
int i,j,i1,j1;
if(dr-st<3)
{
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
Min=min(Min,dst(i,j));
return Min;
}
Min=solve(st,mj);
Min1=solve(mj+1,dr);
Min=min(Min,Min1);
MIN=sqrtl(Min);
for(i=mj;i>=st&&a[mj].x-a[i].x<=MIN;i--);
for(j=mj;j<=dr&&a[j].x-a[mj].x<=MIN;j++);
for(i1=i+1;i1<j;i1++)
for(j1=i1+1;j1<=j;j1++)
Min=min(Min,dst(i1,j1));
return Min;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
printf("%Lf\n",sqrtl(solve(1,n)));
return 0;
}