Pagini recente » Cod sursa (job #2190484) | Cod sursa (job #2937340) | Cod sursa (job #1718185) | Cod sursa (job #985288) | Cod sursa (job #1587136)
#include<cstdio>
#include<algorithm>
#include <cmath>
using namespace std;
int N;
pair < int , int > a[100009], aux[100009];
double dist (pair < int , int > a, pair < int , int > b)
{
return (double) sqrt ((double) (a.first - b.first) * (a.first - b.first) + (double) (a.second - b.second) * (a.second - b.second));
}
bool cmp (pair < int , int > a, pair < int , int > b)
{
return a.second < b.second;
}
double solve (int st, int dr)
{
if (st == dr) return 1e10;
int mij = (st + dr) >> 1;
double median = a[mij].first, ans = solve (st, mij), curr = solve (mij + 1, dr);
if (curr < ans) ans = curr;
int p1 = st, p2 = mij + 1, pos = 0;
while (p1 <= mij || p2 <= dr)
{
if (p2 > dr || (p1 <= mij && a[p1].second < a[p2].second)) aux[++pos] = a[p1 ++];
else aux[++pos] = a[p2 ++];
}
pos = 0;
for (int i=st; i<=dr; i++)
a[i] = aux[++pos];
pos = 0;
for (int i=st; i<=dr; i++)
if (a[i].first >= median - ans && a[i].first <= median + ans) aux[++pos] = a[i];
for (int i=1; i<=pos; i++)
for (int j=i + 1; j<=pos && aux[j].second - aux[i].second < ans; j++)
{
double curr = dist (aux[i], aux[j]);
if (curr < ans) ans = curr;
}
return ans;
}
int main ()
{
freopen ("cmap.in", "r", stdin);
freopen ("cmap.out", "w", stdout);
scanf ("%d", &N);
for (int i=1; i<=N; i++)
scanf ("%d %d", &a[i].first, &a[i].second);
sort (a + 1, a + N + 1);
double ans = solve (1, N);
printf ("%.10f\n", ans);
return 0;
}