Pagini recente » Cod sursa (job #2130073) | Cod sursa (job #2466083) | Cod sursa (job #3158491) | Cod sursa (job #2503097) | Cod sursa (job #3239817)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <vector>
#define double long double
using namespace std;
ifstream cin ("cmap.in");
ofstream cout ("cmap.out");
const double MAX = (double)(4e18);
const int N = 1e5;
struct point
{
int x, y;
const operator < (const point &a)const{
return x < a.x;
}
} a[N + 1], aux[N + 1];
int n, bulan = 8;
double dist (point a, point b)
{
return sqrt(((double)(a.x - b.x) * (double)(a.x - b.x) + (double)(a.y - b.y) * (double)(a.y - b.y)));
}
inline double ab (double x)
{
if (x < 0)return -x;
return x;
}
double divide (int l, int r)
{
if (l == r)
return MAX;
int mid = (l + r) >> 1;
double left_ans = divide (l, mid);
double right_ans = divide (mid + 1, r);
double d = min (left_ans, right_ans);
double center = (double)a[mid].x;
for (int i = l; i <= mid; ++i)
center = max (center, (double)a[i].x);
int st = l, dr = mid + 1, k = 0;
while (st <= mid && dr <= r)
{
if (a[st].y < a[dr].y)
aux[++k] = a[st++];
else if (a[st].y > a[dr].y)
aux[++k] = a[dr++];
else
aux[++k] = a[st++], aux[++k] = a[dr++];
}
while (st <= mid)aux[++k] = a[st], st++;
while (dr <= r)aux[++k] = a[dr], dr++;
for (int i = 1; i <= k; ++i)
a[i + l - 1] = aux[i];
vector <point> p;
for (int i = l; i <= r; ++i)
if (ab (center - a[i].x) <= d)
p.push_back(a[i]);
for (int i = 0; i < p.size(); ++i)
for (int j = i + 1; j < min (i + bulan, (int)(p.size())); ++j)
{
if (d > dist (p[i], p[j]))
d = dist (p[i], p[j]);
}
return d;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i].x >> a[i].y;
sort (a + 1, a + n + 1);
cout << fixed << setprecision(6) << divide (1, n) << '\n';
return 0;
}