Pagini recente » Cod sursa (job #2691934) | Cod sursa (job #2250273) | Cod sursa (job #2920619) | Cod sursa (job #2454486) | Cod sursa (job #1828901)
#include <algorithm>
#include <bitset>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <cstdlib>
using namespace std;
//#include <iostream>
#include <fstream>
ifstream fin ("cmap.in");
ofstream cout ("cmap.out");
const int INF = 2000000000;
const int Nmax = 100000 + 10;
const double EPS = 0.000001;
using int64 = long long;
using PointTemp = pair <int64, int64>;
int N;
vector <PointTemp> P;
PointTemp C[Nmax], Aux[Nmax];
void Input();
inline int64 Dist(const PointTemp&, const PointTemp&);
inline int64 Solve(int64, int64);
int main()
{
Input();
sort(P.begin(), P.end());
for (int i = 0; i < N; ++i)
swap(P[i].first, P[i].second);
cout << fixed << setprecision(6) << sqrt(1.0 * Solve(0, N-1));
};
inline int64 Solve(int64 Left, int64 Right)
{
//cout << Left << ' ' << Right << '\n';
if (Right - Left + 1 < 2) return INF;
if (Right - Left + 1 == 2) return min(Solve(Left, Left), Solve(Right, Right));
int Mid = (Left + Right) / 2;
int DX = P[Mid].first;
int64 Best = min(Solve(Left, Mid), Solve(Mid+1, Right));
merge(P.begin() + Left, P.begin() + Mid + 1, P.begin() + Mid + 1, P.begin() + Right+1, Aux);
int sz = 0;
for (int i = 0; i < Right - Left + 1; ++i)
if (DX - Best <= Aux[i].second && Aux[i].second <= DX + Best)
C[++sz] = Aux[i];
for (int i = 1; i <= sz; ++i)
for (int j = 1; j + i <= sz && j <=7 ; ++j)
Best = min(Best, Dist(C[i], C[i+j]));
return Best;
};
void Input()
{
fin >> N;
for (int i = 1, x, y; i <= N; ++i)
{
fin >> x >> y;
P.push_back({x, y});
}
};
inline int64 Dist(const PointTemp& A, const PointTemp& B)
{
return 1LL * (B.second - A.second) * (B.second - A.second) + 1LL * (B.first - A.first) * (B.first - A.first);
};