Pagini recente » Cod sursa (job #611604) | Cod sursa (job #2383143) | Cod sursa (job #2346565) | Cod sursa (job #1078398) | Cod sursa (job #2089094)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
double maxim,inf=0x3f3f3f;
struct coord
{
int x;
int y;
} puncte[100005],c[100005];
void citire()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
{
scanf("%d %d\n", &puncte[i].x, &puncte[i].y);
}
}
int cmp(coord e,coord f)
{
return (e.x<f.x || e.x==f.x && e.y<f.y);
}
void afisare()
{
for(int i=0; i<n; i++)
cout<<puncte[i].x<<" "<<puncte[i].y<<endl;
}
long long dist(coord e,coord f)
{
return 1LL*(e.x-f.x)*(e.x-f.x)+1ll*(e.y-f.y)*(e.y-f.y);
}
void interclasare(int l, int m, int r)
{
int k = 0, i, j;
for (i = l, j = m + 1; i <= m && j <= r;)
if (puncte[i].x<puncte[j].x || puncte[i].x==puncte[j].x && puncte[i].y<puncte[j].y)
c[k++] = puncte[i++];
else
c[k++] = puncte[j++];
while (i <= m)
c[k++] = puncte[i++];
while (j <= r)
c[k++] = puncte[j++];
for (i = r; i >= l; --i)
puncte[i] = c[k--];
}
double divide(int st, int dr)
{
int cv=0;
long long minim=inf;
if(dr-st<3)
{
for(int i=st; i<dr; i++)
for(int j=i+1; j<=dr; j++)
minim = min(minim, dist(puncte[i], puncte[j]));
sort(puncte+st,puncte+dr+1,cmp);
return minim;
}
int jum=(st+dr)/2;
long long d1 = divide(st, jum);
long long d2 = divide(jum + 1, dr);
if (d1 > d2)
d1 = d2;
minim = d1;
interclasare(st,dr,jum);
for (int i = st; i <= dr; i++)
if ((puncte[i].x - puncte[jum].x) * (puncte[i].x - puncte[jum].x) <= d1)
c[cv++] = puncte[i];
for (int i=0; i<cv; i++)
for (int j = i + 1; j < cv&& j <= i + 7;j++)
dist(c[i], c[j]);
return minim;
}
void afisareeeee()
{
for(int i=0;i<n;i++)
cout<<c[i].x<<" "<<c[i].y<<endl;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
citire();
sort(puncte,puncte+n,cmp);
double rasp=divide(0,n-1);
printf("%llf",sqrt(rasp));
//afisare();
return 0;
}