Pagini recente » Cod sursa (job #2763586) | Cod sursa (job #729653) | Cod sursa (job #2787270) | Cod sursa (job #778221) | Cod sursa (job #2369496)
#include <bits/stdc++.h>
#define llg long long
#define llg_pair std::pair <llg, llg>
#define x first
#define y second
llg dist2(const llg_pair& p0, const llg_pair& p1) {
return (p0.y - p1.y) * (p0.y - p1.y) + (p0.x - p1.x) * (p0.x - p1.x);
}
#define MAXN 100005
#define INF 40000000000000005
int N;
#define _Middle (Left+Right)/2
std::vector <llg_pair> V(MAXN);
std::vector <llg_pair> A, B;
llg DivideEtImpera(int Left = 0, int Right = N, std::vector <llg_pair>& A = A, std::vector <llg_pair>& B = B) {
if (Left+1 >= Right) return INF;
if (Left+2 == Right) {
if (B[Left] > B[Left+1])
std::swap(B[Left], B[Left+1]);
return dist2(A[Left], A[Left+1]);
} llg Min = std::min(DivideEtImpera(Left, _Middle, A, B), DivideEtImpera(_Middle, Right, A, B));
std::merge(B.begin() + Left, B.begin() + _Middle, B.begin() + _Middle, B.begin() + Right, V.begin());
std::copy(V.begin(), V.begin() + (Right-Left), B.begin() + Left);
int replace = 0;
for (int i=Left, j; i<Right; ++i)
if (abs(B[i].second - A[_Middle].first) <= Min)
V[replace++] = B[i];
for (int i=0, j; i<replace; ++i)
for (j=i+1; j<replace && j < i+8; ++j)
Min = std::min(Min, dist2(V[j], V[i]));
return Min;
}
std::ifstream In ("cmap.in");
std::ofstream Out("cmap.out");
void Citire() {
In >> N;
for (int i=0, X, Y; i<N; ++i)
In >> X >> Y, A.push_back({X, Y});
}
void Rezolvare() {
std::sort(A.begin(), A.end());
for (int i=0; i<N; ++i)
B.push_back(A[i]);
Out << std::fixed << std::setprecision(6) << sqrt(double(DivideEtImpera())) << '\n';
}
int main()
{
Citire();
Rezolvare();
return 0;
}