Pagini recente » Cod sursa (job #2133943) | Cod sursa (job #2843964) | Cod sursa (job #2495539) | Cod sursa (job #2172376) | Cod sursa (job #1097291)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#define ll long long
#define ff first
#define ss second
#define mid ((st + dr) >> 1)
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int Nmax = 1e5 + 100;
const ll OO = (1LL << 60);
typedef pair <ll, ll> pct;
int N;
vector <pct> X(Nmax), Y(Nmax), V(Nmax);
ll Dist(pct A, pct B)
{
return (A.ff - B.ff) * (A.ff - B.ff) + (A.ss - B.ss) * (A.ss - B.ss);
}
ll DivImp(int st, int dr)
{
if(st >= dr - 1) return OO;
if(dr - st == 2)
{
if(Y[st] > Y[st + 1])
swap(Y[st], Y[st + 1]);
return Dist(X[st], X[st + 1]);
}
ll best = min(DivImp(st, mid), DivImp(mid, dr));
merge(Y.begin() + st, Y.begin() + mid, Y.begin() + mid, Y.begin() + dr, V.begin());
copy(V.begin(), V.begin() + (dr - st), Y.begin() + st);
int vsize = 0;
for(int i = st; i < dr; i++)
if(abs(Y[i].ss - X[mid].ff) <= best)
V[++vsize] = Y[i];
for(int i = 1; i <= vsize; i++)
for(int j = i + 1; j <= vsize && j - i < 8; j++)
best = min(best, Dist(V[i], V[j]));
return best;
}
int main()
{
fin >> N;
for(int i = 0; i < N; i++)
fin >> X[i].ff >> X[i].ss;
sort(X.begin(), X.begin() + N);
for(int i = 0; i < N; i++)
Y[i] = pct(X[i].ss, X[i].ff);
fout.precision(6);
fout << fixed << sqrt(DivImp(0, N));
return 0;
}