Pagini recente » Cod sursa (job #1499666) | Cod sursa (job #456197) | Cod sursa (job #1676346) | Cod sursa (job #416139) | Cod sursa (job #2188735)
#include <bits/stdc++.h>
#define INF 4e18
#define ll long long
#define dimn 100005
#define y first
#define x second
typedef std::pair <ll, ll> punct;
int N;
std::vector <std::pair <ll, ll> > X, Y, V(dimn);
std::ifstream f("cmap.in");
std::ofstream g("cmap.out");
ll dist2(punct A, punct B) {
return (A.y - B.y)*(A.y - B.y) + (A.x - B.x)*(A.x - B.x);
}
ll divetimp(int st=0, int dr=X.size(), std::vector <punct> &X=X, std::vector <punct> &Y=Y) {
if(st>=dr - 1)
return INF;
if(dr-st == 2) {
if(Y[st] > Y[st+1])
std::swap(Y[st], Y[st+1]);
return dist2(X[st], X[st+1]);
}
int m = (st+dr)/2;
ll min = std::min(divetimp(st, m, X, Y), divetimp(m, dr, X, Y));
std::merge(Y.begin()+st, Y.begin()+m, Y.begin()+m, Y.begin()+dr, V.begin());
std::copy(V.begin(), V.begin() + (dr-st), Y.begin()+st);
int ts = 0;
for (int i=st; i<dr; i++) {
if(abs(Y[i].second - X[m].first) <= min)
V[ts++] = Y[i];
}
for(int i=0, j; i<ts; i++) {
for(j=i+1; j<ts && j-i < 8; j++)
min = std::min(min, dist2(V[j], V[i]));
}
return min;
}
void citire() {
f >> N;
int x, y;
for (int i=1; i<=N; i++) {
f >> x >> y;
X.push_back({x, y});
}
}
void rezolvare() {
std::sort(X.begin(), X.end());
for (int i=0; i<N; i++)
Y.push_back(std::make_pair(X[i].x, X[i].y));
g << std::fixed << std::setprecision(6) << sqrt(1.0 * divetimp()) << "\n";
}
int main()
{
citire();
rezolvare();
return 0;
}