Pagini recente » Cod sursa (job #2103769) | Cod sursa (job #858543) | Cod sursa (job #419028) | Cod sursa (job #1149536) | Cod sursa (job #3178751)
#include <fstream>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#define sz 100005
long long INF = LLONG_MAX;
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
struct poz{
long long x;
long long y;};
poz v[sz + 5];
long long dist(poz a,poz b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
long long divide_imp(int st,int dr)
{
if(dr-st+1<=3)
{
long long md = INF;
for(int i = st;i<dr;i++)
for(int j = i + 1;j<=dr;j++)
if(dist(v[i],v[j]) < md)
md = dist(v[i],v[j]);
return md;
}
int mid = (st+dr)/2;
long long d = min(divide_imp(st,mid),divide_imp(mid+1,dr));
poz aux[dr-st+2];
int k = 0;
for(int i = st; i<=dr ; i++)
if( (v[i].x - v[mid].x)*(v[i].x-v[mid].x) < d)
aux[++k] = v[i];
sort(aux + 1,aux + k + 1,[](poz a,poz b){return a.y<b.y;});
for(int i = 1;i<=k;i++)
for(int j = i+1;j<=k && (aux[i].y-aux[j].y)*(aux[i].y-aux[j].y) < d;j++)
d=min(d,dist(aux[i],aux[j]));
return d;
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,[](poz a,poz b){return a.x<b.x;});
long long sol = divide_imp(1,n);
fout<<fixed<<setprecision(6)<<sqrt(sol);
}