Pagini recente » Cod sursa (job #2345614) | Cod sursa (job #854134) | Cod sursa (job #738286) | Cod sursa (job #290376) | Cod sursa (job #1584114)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define NMAX 100002
#define INF 2000000001
using namespace std;
struct punct
{
long long x,y;
}X[NMAX],Y[NMAX],A;
bool compX(punct a,punct b)
{
if(a.x<b.x)
return true;
if(a.x>b.x)
return false;
else
{
if(a.y<b.y)
return true;
else return false;
}
}
bool compY(punct a,punct b)
{
if(a.y<b.y)
return true;
else
return false;
}
int n;
double distanta(punct a,punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double divide(int st,int dr)
{
double dist,minim,m;
if(dr-st+1<=3)
{
dist = INF;
for(int i=st;i<=dr;i++)
{
for(int j=i+1;j<=dr;j++)
dist = min(distanta(X[i],X[j]),dist);
}
sort(Y+st,Y+dr+1,compY);
return dist;
}
else
{
int mij = (st+dr)/2;
minim = min(divide(st,mij),divide(mij+1,dr));
punct temp[dr-st+2];
merge(Y+st,Y+mij+1,Y+mij+1,Y+dr+1,temp+1,compY);
copy(temp+1,temp+dr-st+2,Y+st);
for(int i=st;i<=dr;i++)
{
for(int j=1;j<=7 && i+j<=dr && Y[i+j].y-Y[i].y<=minim;j++)
{
minim = min(minim,distanta(Y[i],Y[i+j]));
}
}
return minim;
}
}
ifstream in("cmap.in");
ofstream out("cmap.out");
int main()
{
in >> n;
for(int i=1;i<=n;i++)
{
in >> A.x >> A.y;
X[i] = A; Y[i] = A;
}
sort(X+1,X+n+1,compX);
out << fixed << setprecision(6) << divide(1,n);
return 0;
}