Pagini recente » Cod sursa (job #2127978) | Cod sursa (job #579536) | Cod sursa (job #804182) | Cod sursa (job #1006621) | Cod sursa (job #1536294)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX 100010
#define x first
#define y second
#define INF (~(1ll<<63))
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pair<int, int> a[MAX], b[MAX], c[MAX];
long long dist(pair<int, int> a, pair<int, int> b)
{
return 1LL * (b.second - a.second) * (b.second - a.second) + 1ll * (b.first - a.first) * (b.first - a.first);
}
long long rez(int st, int dr)
{
if(st == dr)
return INF;
if(st == dr - 1)
return dist(a[st], a[dr]);
int mij = (st + dr) >> 1;
long long d = min(rez(st, mij), rez(mij + 1, dr));
int dr2 = 0, i, j;
pair<int, int> pct = a[mij];
for(i = st ; i <= dr ; i++)
if(a[i].second - d <= pct.second && a[i].second + d >= pct.second)
b[++dr2] = a[i];
merge(a + st, a + mij + 1, a + mij + 1, a + dr + 1, c + st);
for(i = st ; i <= dr ; i++)
a[i] = c[i];
for(i = 1 ; i <= dr2 ; i ++)
{
for(j = i + 1 ; j <= dr2 ; j++)
{
if(d < 1ll * (b[j].first - b[i].first) * (b[j].first - b[i].first))
break;
d = min(d, dist(b[i], b[j]));
}
}
return d;
}
int main()
{
int n, i;
fin >> n;
for(i = 1 ; i <= n ; i++)
fin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1);
for(i = 1 ; i <= n ; i++)
swap(a[i].first, a[i].second);
fout << fixed << setprecision(6) << sqrt(rez(1, n)) << "\n";
}