Pagini recente » Cod sursa (job #2733269) | Cod sursa (job #51330) | Cod sursa (job #2798258) | Cod sursa (job #2799632) | Cod sursa (job #1769365)
#include <iostream>
#include <fstream>
#include <limits.h>
#include <algorithm>
#include <math.h>
#define MLen 100005
using namespace std;
ofstream fout("cmap.out");
ifstream fin ("cmap.in");
struct tip
{
int x, y;
} pct[MLen],sec[MLen];
int iy[MLen],n,aux[MLen];
long long rasp=LLONG_MAX;
long long minim(long long a, long long b)
{
if(a<b)return a;return b;
}
long long dist(tip a,tip b)
{
int x=a.x-b.x, y=a.y-b.y;
return ((long long)((x*x)+(y*y)));
}
// interclasari pe x si y
void interc(int st, int m, int dr)
{
int i=st, j=m+1,k=st;
while(k<=dr)
{
if((i<=m)&&(pct[i].x<=pct[j].x))
sec[k++]=pct[i++];
if((j<=dr)&&(pct[j].x<=pct[i].x))
sec[k++]=pct[j++];
if(i>m)while(j<=dr)sec[k++]=pct[j++];
if(j>dr) while(i<=m)sec[k++]=pct[i++];
}
for(k=st; k<=dr; ++k)pct[k]=sec[k];
}
void intercy(int st, int m, int dr)
{
int i=st, j=m+1,k=st;
while(k<=dr)
{
if((i<=m)&&(pct[iy[i]].y<=pct[iy[j]].y))
aux[k++]=iy[i++];
if((j<=dr)&&(pct[iy[j]].y<=pct[iy[i]].y))
aux[k++]=iy[j++];
if(i>m)while(j<=dr)aux[k++]=iy[j++];
if(j>dr) while(i<=m)aux[k++]=iy[i++];
}
for(k=st; k<=dr; ++k)iy[k]=aux[k];
}
// sortare pe x si y
void srt(int st, int dr)
{
int m=(st+dr)/2;
if(st<dr)
{
srt(st,m);
srt(m+1,dr);
interc(st,m,dr);
}
return;
}
void srty(int st, int dr)
{
int m=(st+dr)/2;
if(st<dr)
{
srty(st,m);
srty(m+1,dr);
intercy(st,m,dr);
}
return;
}
void genesa (int st, int dr)
{
int m=(st+dr)/2,l=pct[m].x;
if(dr-st<3)
{
for(int i=st;i<dr; ++i)
for(int j=i+1; j<=dr; ++j)
{
long long h=dist(pct[i],pct[j]);
rasp=minim(rasp,h);
}
return;
}
genesa (st, m);
genesa (m+1,dr);
int k=st;
for(int i=st; i<=dr; ++i)
{
if((long long)(pct[i].x-l)*(pct[i].x-l)<rasp)iy[k++]=i;
}
k--;
srty(st,k);
for(int i=st;i<k;i++)
for(int j=i+1;j<=k&&j<=i+8;j++)
{
long long h=dist(pct[iy[i]],pct[iy[j]]);
rasp=minim(rasp,h);
}
}
int main()
{
fin>>n;
for(int i=0; i<n; ++i)fin>>pct[i].x>>pct[i].y,iy[i]=i;
srt(0,n-1);
for(int i=0;i<n;i++)
genesa(0,n-1);
fout<<sqrt(rasp);
return 0;
}