Pagini recente » Cod sursa (job #1049487) | Cod sursa (job #2287574) | Cod sursa (job #1268192) | Cod sursa (job #1482771) | Cod sursa (job #687650)
Cod sursa(job #687650)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#define Infinity 2000000000
#define x first
#define y second
#define pdd pair <double, double>
#define NMax 100005
using namespace std;
int N;
pdd X[NMax], Y[NMax], Aux[NMax];
inline double Distance (pdd A, pdd B)
{
return sqrt ((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
inline double Solve (int L, int R)
{
if (L+1>=R) return Infinity;
if (L+2==R)
{
sort (Y+L, Y+R);
return Distance (X[L], X[R-1]);
}
int Mid=(L+R)/2;
double DMin=min (Solve (L, Mid), Solve (Mid, R));
merge (Y+L, Y+Mid, Y+Mid, Y+R, Aux);
copy (Aux, Aux+R-L, Y+L);
vector <pdd> P;
for (int i=L; i<R; ++i)
{
if (abs(Y[i].y-X[Mid].x)<=DMin)
{
P.push_back (Y[i]);
}
}
for (int i=0; i<P.size (); ++i)
{
for (int j=i+1; j<P.size () and j-i<8; ++j)
{
DMin=min (DMin, Distance (P[i], P[j]));
}
}
return DMin;
}
void Read ()
{
freopen ("cmap.in", "r", stdin);
scanf ("%d", &N);
for (int i=0; i<N; ++i)
{
scanf ("%lf %lf", &X[i].x, &X[i].y);
}
sort (X, X+N);
for (int i=0; i<N; ++i)
{
Y[i].x=X[i].y, Y[i].y=X[i].x;
}
}
void Print ()
{
freopen ("cmap.out", "w", stdout);
printf ("%.6lf\n", Solve (0, N));
}
int main()
{
Read ();
Print ();
return 0;
}