Pagini recente » Cod sursa (job #1235964) | Diferente pentru preoni-2007/runda-finala/poze/deschidere intre reviziile 6 si 3 | Cod sursa (job #1813092) | Cod sursa (job #2028063) | Cod sursa (job #2089078)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#define NMAX 100005
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n;
pair <int, int> p[NMAX], v[NMAX];
ll minim;
ll distantaPuncte2(pair<int, int> a, pair<int, int> b)
{
ll x = (a.first - b.first) * 1LL;
ll y = (a.second - b.second) * 1LL;
return x * x + y * y;
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
if(a.first < b.first || (a.first == b.first && a.second < b.second))
return true;
return false;
}
void read()
{
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%d %d", &p[i].first, &p[i].second);
sort(p+1, p + n + 1);
}
ll solveBrut(int left, int right)
{
ll minimAux = INF;
for(int i = left; i < right; ++i)
for(int j = i + 1; j <= right; ++j)
minimAux = min(minimAux, distantaPuncte2(p[i], p[j]));
return minimAux;
}
void mergeSort(int l, int m, int r)
{
int k = 0, i, j;
for(i = l, j = m + 1; i <= m && j <= r; )
if(cmp(p[i], p[j]) == true)
v[++k] = p[i++];
else
v[++k] = p[j++];
while(i <= m)
v[++k] = p[i++];
while(j <= r)
v[++k] = p[j++];
for(j = r; j >= l; --j)
p[j] = v[k--];
}
ll solve(int l, int r)
{
if(r - l < 3)
return solveBrut(l, r);
int mijloc = (r + l)/2;
ll d1 = solve(1, mijloc), d2 = solve(mijloc + 1, r);
minim = min(d1, d2);
mergeSort(l, mijloc, r);
int k = 0;
for(int i = l; i <= r; ++i)
if((p[i].first - p[mijloc].first) * (p[i].first - p[mijloc].first) < minim)
v[++k] = p[i];
for(int i = 1; i < k; ++i)
for(int j = i+1; j <= i+7 && j <= k; ++j)
minim = min(minim, distantaPuncte2(v[i], v[j]));
return minim;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
read();
printf("%.6lf", sqrt(solve(1, n)));
return 0;
}