Pagini recente » Cod sursa (job #2858912) | Cod sursa (job #1443743) | Cod sursa (job #1203743) | Cod sursa (job #2570757) | Cod sursa (job #2836566)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int N = 1e5 + 5;
const double INF = 1e20;
struct Point {
double x, y;
};
Point v[N];
bool cmp_x(const Point& p1, const Point& p2) {
return p1.x < p2.x;
}
bool cmp_y(const Point& p1, const Point& p2) {
return p1.y < p2.y;
}
double calc(int st, int dr) {
if (dr - st <= 1)
return INF;
int m = (st + dr) / 2;
double l_st = calc(st, m);
double l_dr = calc(m, dr);
double l = min(l_st, l_dr);
double x_sep = v[m].x;
vector<Point> a;
for (int i = 0; i < m; ++i)
if (v[i].x >= x_sep - l)
a.push_back(v[i]);
vector<Point> b;
for (int i = m; i < dr; ++i)
if (v[i].x <= x_sep + l)
b.push_back(v[i]);
sort(a.begin(), a.end(), cmp_y);
sort(b.begin(), b.end(), cmp_y), cmp_y;
int pst, pdr;
pst = pdr = 0;
double l_fin = l;
for (auto p: a) {
while (pdr < b.size() && b[pdr].y <= a[pdr].y + l)
++pdr;
while (pst < b.size() && a[pst].y < a[pdr].y - l)
++pst;
if (pst == b.size())
break;
for (int i = pst; i < pdr; ++i)
l_fin = min(l_fin, (p.x - b[i].x) * (p.x - b[i].x) + (p.y - b[i].y) * (p.y - b[i].y));
}
return l_fin;
}
int main() {
ifstream cin("cmap.in");
ofstream cout("cmap.out");
int n;
cin >> n;
for (int i = 0; i < n; ++i)
cin >> v[i].x >> v[i].y;
cin.close();
sort(v, v + n, cmp_x);
cout << fixed << setprecision(6) << sqrt(calc(0, n)) << "\n";
cout.close();
return 0;
}