Pagini recente » Cod sursa (job #2574678) | Cod sursa (job #1811758) | Cod sursa (job #1913388) | Cod sursa (job #1916925) | Cod sursa (job #3321618)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Punct {
double x, y;
};
vector<Punct> p, aux;
double dist(const Punct &a, const Punct &b) {
double dx = a.x - b.x, dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
double divide(int st, int dr) {
if (dr - st <= 3) {
double d = 1e18;
for (int i = st; i < dr; ++i) {
for (int j = i + 1; j <= dr; ++j) {
d = min(d, dist(p[i], p[j]));
}
}
sort(p.begin() + st, p.begin() + dr + 1, [](const Punct &a, const Punct &b) {
return a.y < b.y;
});
return d;
}
int mid = (st + dr) / 2;
double xmid = p[mid].x;
double d = min(divide(st, mid), divide(mid + 1, dr));
merge(p.begin() + st, p.begin() + mid + 1, p.begin() + mid + 1, p.begin() + dr + 1, aux.begin(), [](const Punct &a, const Punct &b) {
return a.y < b.y;
});
copy(aux.begin(), aux.begin() + (dr - st + 1), p.begin() + st);
int cnt = 0;
for (int i = st; i <= dr; ++i) {
if (fabs(p[i].x - xmid) <= d) {
aux[cnt++] = p[i];
}
}
for (int i = 0; i < cnt; ++i) {
for (int j = i + 1; j < cnt && (aux[j].y - aux[i].y) < d; ++j) {
d = min(d, dist(aux[i], aux[j]));
}
}
return d;
}
int main() {
int n;
fin >> n;
p.resize(n);
aux.resize(n);
for (int i = 0; i < n; ++i) {
fin >> p[i].x >> p[i].y;
}
fin.close();
sort(p.begin(), p.end(), [](const Punct &a, const Punct &b) {
return a.x < b.x;
});
fout.precision(6);
fout << fixed << divide(0, n - 1) << "\n";
fout.close();
return 0;
}