Pagini recente » Cod sursa (job #2804616) | Cod sursa (job #2116837) | Cod sursa (job #485885) | Cod sursa (job #1422386) | Cod sursa (job #1379329)
#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 << 61);
if (st + 1 == dr)
{
if ( P[st].y > P[dr].y )
swap(P[st], P[dr]);
return D(P[st], P[dr]);
}
int m = (st + dr) / 2;
int med = P[m].x;
long long d1 = dist(st, m);
long long d2 = dist(m + 1, dr);
long long d = min(d1, d2);
int i = st, j = m + 1, k = st;
while (i <= m && j <= dr)
{
if ( P[i].y <= P[j].y )
auxP[k++] = P[i++];
else
auxP[k++] = P[j++];
}
while (i <= m) auxP[k++] = P[i++];
while (j <= dr) auxP[k++] = P[j++];
for (int k = st; k <= dr; ++k)
P[k] = auxP[k];
int nr = 0;
for (int k = st; k <= dr; ++k)
if ( abs(P[k].x - med) <= 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]));
j--;
cnt--;
}
}
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;
}