Pagini recente » Cod sursa (job #812553) | Cod sursa (job #1820726) | Cod sursa (job #223112) | Cod sursa (job #418059) | Cod sursa (job #2836550)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const double INF = 1e20;
struct Point {
double x, y;
};
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(vector<Point> v) {
if (v.size() <= 1)
return INF;
double l_st = calc(vector<Point>(v.begin(), v.begin() + v.size() / 2));
double l_dr = calc(vector<Point>(v.begin() + v.size() / 2, v.end()));
double l = min(l_st, l_dr);
double x_sep = v[v.size() / 2].x;
vector<Point> a;
for (int i = 0; i < v.size() / 2; ++i)
if (v[i].x >= x_sep - l)
a.push_back(v[i]);
vector<Point> b;
for (int i = v.size() / 2; i < v.size(); ++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 st, dr;
st = dr = 0;
double l_fin = l;
for (auto p: a) {
while (dr < b.size() && b[dr].y <= a[dr].y + l)
++dr;
while (st < b.size() && a[st].y < a[dr].y - l)
++st;
if (st == b.size())
break;
for (int i = st; i < dr; ++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;
vector<Point> p;
for (int i = 0; i < n; ++i) {
double x, y;
cin >> x >> y;
p.push_back({x, y});
}
cin.close();
sort(p.begin(), p.end(), cmp_x);
cout << fixed << setprecision(6) << sqrt(calc(p)) << "\n";
cout.close();
return 0;
}