Pagini recente » Cod sursa (job #3129448) | Cod sursa (job #2901530) | Cod sursa (job #3141176) | Cod sursa (job #1319100) | Cod sursa (job #1690691)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define MAX 100010
#define INF (1ll<<61)
typedef long long ll;
pair<int, int> a[MAX], b[MAX], c[MAX];
ll dist(pair<int, int> a, pair<int, int> b)
{
return 1ll * (a.first - b.first) * (a.first - b.first)+
1ll * (a.second - b.second) * (a.second - b.second);
}
ll ans(int st, int dr)
{
//cout << st << " " << dr << "\n";
int j, i;
if(st == dr)
return INF;
if(st + 1 == dr)
return dist(a[st], a[dr]);
int mij = (st + dr) >> 1;
int line = a[mij].first;
long long delta = min(ans(st, mij), ans(mij + 1, dr));
merge(a + st, a + mij + 1, a + mij + 1, a + dr + 1, b + st);
int dr2 = 0;
for(i = st ; i <= dr ; i ++)
{
a[i] = b[i];
if(abs(a[i].first - line) <= delta)
{
b[++dr2] = a[i];
}
}
for(i = 1 ; i <= dr2 ; i ++)
{
for(j = i + 1 ; j <= i + 10 && j <= dr2 ; j++)
{
delta = min(delta, dist(a[i], a[j]));
}
}
return delta;
}
int main()
{
int n, i;
fin >> n;
for(i = 1 ; i <= n ; i++)
{
fin >> a[i].first >> a[i].second;
}
sort(a + 1, a + n + 1);
for(i = 1 ; i <= n ;i++)
{
swap(a[i].first, a[i].second);
}
fout << fixed << setprecision(8) << sqrt(ans(1, n)) << "\n";
}