Pagini recente » Cod sursa (job #3199315) | Cod sursa (job #2557561) | Cod sursa (job #1253926) | Cod sursa (job #2689609) | Cod sursa (job #1415179)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define INF (~(1LL<<63))
#define MAX 100010
typedef long long ll;
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);
}
pair<int, int> a[MAX], b[MAX], c[MAX];
ll rez(int st, int dr)
{
if(st == dr)
return INF;
if(st == dr - 1)
return dist(a[st], a[dr]);
int mij = (st + dr) / 2;
int dreapta = a[mij].second;
ll val = min(rez(st, mij), rez(mij + 1, dr));
merge(a + st, a + mij + 1, a + mij + 1, a + dr + 1, b);
int x = 0;
for(int i = 0 ; i <= dr - st ; i++)
{
if(1LL * (b[i].second - dreapta) * (b[i].second - dreapta) <= val)
{
c[++x] = b[i];
a[i + st] = b[i];
}
}
for(int i = 1 ; i <= x ; i++)
{
for(int j = 1 ; j <= 7 && i + j <= x; j++)
{
val = min(val, dist(c[i], c[i + j]));
}
}
return val;
}
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 << setprecision(6) << fixed << sqrt(1LL * rez(1, n)) << "\n";
}