Pagini recente » Cod sursa (job #2306984) | Cod sursa (job #1490204) | Cod sursa (job #2304782) | Cod sursa (job #1495680) | Cod sursa (job #1573520)
#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];
void citire()
{
int x, y;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &x, &y);
v[i] = coord(x, y);
}
sort (v+1, v+1+n, cmpAbscisa);
}
double solve(int st, int dr, vector<coord> &y)
{
if (dr - st <= 0) {
y.push_back(v[st]);
return inf;
}
// else if (dr - st <= 1) {
// if (v[st].y < v[dr].y)
// y.push_back(v[st]), y.push_back(v[dr]);
// else
// y.push_back(v[dr]), y.push_back(v[st]);
// return dist(v[st], v[dr]);
// }
int mid = (st+dr)/2;
vector<coord> p1, p2;
double best = min(solve(st, mid, p1), solve(mid+1, dr, p2));
for (int i = 0, j = 0, t1 = p1.size(), t2 = p2.size(); i < t1 || j < t2; ) {
coord e;
if (j >= t2 || i < t1 && p1[i].y < p2[j].y)
e = p1[i++];
else
e = p2[j++];
//if (abs(e.x - v[mid]) < best)
y.push_back(e);
}
for (int i = 0, t = y.size(); i < t; i++)
for (int j = i+1; j <= i+8 && j < t; j++)
if (dist(y[i], y[j]) < best)
best = dist(y[i], y[j]);
return best;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
vector<coord> iy;
citire();
double rez = solve(1, n, iy);
printf("%.6lf", rez);
return 0;
}