Pagini recente » Cod sursa (job #736138) | Cod sursa (job #276170) | Cod sursa (job #45884) | Cod sursa (job #1019637) | Cod sursa (job #1379135)
#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);
}
long long dist(int st, int dr)
{
if (st >= dr)
return (1LL << 60);
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);
int nr = 0;
for (int k = st; k <= dr; ++k)
if ( D(P[k], P[m]) < 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;
}