Pagini recente » Cod sursa (job #685314) | Cod sursa (job #244575) | Cod sursa (job #402623) | Cod sursa (job #2907377) | Cod sursa (job #3342691)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#define NMax 100005
#define inf 2000000000000000000LL
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
int x,y;
} p[NMax],y[NMax];
int n;
bool crescy(punct a,punct b)
{
if(a.y<b.y)
return 1;
else if(a.y==b.y)
{
if(a.x<b.x)
return 1;
}
return 0;
}
bool crescx(punct a,punct b)
{
if(a.x<b.x)
return 1;
else if(a.x==b.x)
{
if(a.y<b.y)
return 1;
}
return 0;
}
long long int rez(int st, int dr)
{
int mijx;
long long int mn=inf;
int mij=(st+dr)/2;
if(dr-st+1<=3)
{
for(int i=st; i<dr; i++)
{
for(int j=i+1; j<=dr; j++)
{
long long int dx=p[i].x-p[j].x;
long long int dy=p[i].y-p[j].y;
mn=min(mn,dx*dx+dy*dy);
}
}
sort(p+st+1,p+dr+1,crescy);
return mn;
}
else
{
mijx=p[mij].x;
mn=min(rez(st,mij),rez(mij+1,dr));
}
sort(p+st+1,p+dr+1,crescy);
for(int i=st; i<=dr; i++)
{
for(int j=i+1; j<=i+7 && j<=dr; j++)
{
if(1LL*(p[i].x-mijx)*(p[i].x-mijx)<=mn)
{
long long int dx=p[i].x-p[j].x;
long long int dy=p[i].y-p[j].y;
mn=min(mn,dx*dx+dy*dy);
}
}
}
return mn;
}
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>p[i].x>>p[i].y;
}
sort(p+1,p+n+1,crescx);
fout<<fixed<< setprecision(6)<<sqrt(rez(1,n));
return 0;
}