Pagini recente » Cod sursa (job #2298943) | Cod sursa (job #2655431) | Cod sursa (job #1045872) | Cod sursa (job #2137246) | Cod sursa (job #1510043)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define MAX 100100
#define x first
#define y second
pair<int, int> a[MAX], b[MAX];
long long dist(pair<int, int> a, pair<int, int> b)
{
return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}
long long de(int st, int dr)
{
int i, j;
if(st == dr)
return (1ll<<60);
if(st + 1 == dr)
return dist(a[st], a[dr]);
int mij = (st + dr) >> 1;
long long d = min(de(st, mij), de(mij + 1, dr));
merge(a + st, a + mij + 1, a + mij + 1, a + dr + 1, b + 1);
dr = 0;
for(i = 1 ; i <= (dr - st + 1) ; i++)
if(b[i].x + d >= a[mij].x && b[i].x - d <= a[mij].x)
b[++dr] = b[i];
for(i = 1 ; i <= dr ; i++)
for(j = i + 1 ; b[i].x + d <= b[j].x ; j++)
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].x, a[i].y);
}
fout << fixed << setprecision(6) << sqrt(1.0 * de(1, n)) << '\n';
}