Pagini recente » Cod sursa (job #31079) | Cod sursa (job #2133178) | Cod sursa (job #443524) | Cod sursa (job #2349066) | Cod sursa (job #1370744)
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define NMAX 100005
#define LL long long
#define INF 1000000000000000
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector < pair <int, int> > X, Y, Aux;
LL dist(pair<int, int> &P, pair<int, int> &Q)
{
return (LL)(P.first - Q.first) * (P.first - Q.first) + (LL)(P.second - Q.second) * (P.second - Q.second);
}
LL divide(int st, int dr)
{
if (st >= dr - 1) return INF;
if (dr - st == 2)
{
if (Y[st] > Y[st+1])
swap(Y[st], Y[st+1]);
return dist(X[st], X[st+1]);
}
int mij = st + ((dr - st) >> 1);
LL best = min (divide(st, mij), divide(mij, dr));
merge(Y.begin() + st, Y.begin() + mij, Y.begin() + mij, Y.begin() + dr, Aux.begin());
copy(Aux.begin(), Aux.begin() + (dr - st), Y.begin() + st);
int asize = -1;
for (int i = st; i < dr; ++i)
if (abs(Y[i].second - X[mij].first) <= best)
Aux[++asize] = Y[i];
for (int i = 0; i < asize; ++i)
for (int j = i+1; (j < asize) && (j - i < 8); ++j)
best = min(best, dist(Aux[i], Aux[j]));
return best;
}
int main()
{
int n;
fin >> n;
X.resize(n); Y.resize(n); Aux.resize(n);
for (int i = 0; i < n; ++i)
fin >> X[i].first >> X[i].second;
sort(X.begin(), X.begin() + n);
for (int i = 0; i < n; ++i)
Y[i] = {X[i].second, X[i].first};
fout << fixed << setprecision(6) << sqrt(divide(0, n)) << '\n';
return 0;
}