Pagini recente » Cod sursa (job #473692) | Rating Stefan Busila (StefanFurtuna) | Cod sursa (job #3126591) | Cod sursa (job #1915099) | Cod sursa (job #1379145)
#include <bits/stdc++.h>
using namespace std;
#define Point pair<int,int>
#define x first
#define y second
const int Nmax = 100000;
Point P[Nmax];
Point auxP[Nmax];
int N;
long long D(Point A, Point B)
{
return 1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y);
}
bool cmp(Point A, Point B)
{
return A.y < B.y;
}
long long dist(int st, int dr)
{
if (st >= dr)
return (1LL << 61);
if (st + 1 == dr)
return D(P[st], P[dr]);
int m = (st + dr) / 2;
long long d1 = dist(st, m);
long long d2 = dist(m + 1, dr);
long long d = min(d1, d2);
inplace_merge(P + st, P + m, P + dr, cmp);
int nr = 0;
for (int k = st; k <= dr; ++k)
if ( abs(P[k].x - P[m].x) <= d )
auxP[nr++] = P[k];
for (int i = 0; i < nr; ++i)
{
int cnt = 8;
int j = i - 1;
while (j-- >= 0 && cnt-- > 0)
d = min(d, D(auxP[i], auxP[j]));
}
return d;
}
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
in >> N;
for ( int i = 0; i < N; ++i )
in >> P[i].x >> P[i].y;
sort(P, P + N);
out << fixed << setprecision(10);
out << sqrt(dist(0, N - 1)) << "\n";
return 0;
}