Pagini recente » Cod sursa (job #2924556) | Cod sursa (job #2870450) | Cod sursa (job #1329132) | Cod sursa (job #2818349) | Cod sursa (job #1573673)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#define MAXN 100100
#define inf 4e18
using namespace std;
struct coord
{
int x, y;
coord(int x = 0, int y = 0) : x(x), y(y) { }
};
int cmpAbscisa(coord a, coord b)
{
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
double dist(coord a, coord b)
{
double rez = sqrt(((double)a.x - b.x)*(a.x - b.x) + ((double)a.y - b.y) * (a.y - b.y));
return rez;
}
int n;
coord v[MAXN], y[MAXN], aux[MAXN];
void citire()
{
int x, yu;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &x, &yu);
v[i] = coord(x, yu);
}
sort (v+1, v+1+n, cmpAbscisa);
for (int i = 1; i <= n; i++)
y[i] = v[i];
}
double solve(int st, int dr)
{
if (dr - st <= 0)
return inf;
if (dr - st <= 1) {
if (y[st].y > y[dr].y) swap(y[st], y[dr]);
return dist(y[st], y[dr]);
}
int mid = (st+dr)/2;
double best = min(solve(st, mid), solve(mid+1, dr));
/// left = [st, mid], right = [mid+1, dr]
for (int i = st, j = mid+1, t1 = mid+1, t2 = dr+1, k = st; i < t1 || j < t2; k++) {
coord e;
if (j >= t2 || i < t1 && y[i].y < y[j].y)
e = y[i++];
else
e = y[j++];
aux[k] = e;
}
for (int i = st; i <= dr; i++)
y[i] = aux[i];
int k = 0;
for (int i = st; i <= dr; i++)
if (abs(y[i].x - v[mid].x) <= best+1)
aux[k++] = y[i];
for (int i = 0, t = k; i < t; i++)
for (int j = i+1; j <= i+7 && j < t; j++)
if (dist(aux[i], aux[j]) < best)
best = dist(aux[i], aux[j]);
return best;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
citire();
double rez = solve(1, n);
printf("%.6lf", rez);
return 0;
}