Pagini recente » Cod sursa (job #1607084) | Cod sursa (job #491383) | Cod sursa (job #2168239) | Istoria paginii utilizator/coronavirus | Cod sursa (job #2486397)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
#define x first
#define y second
ifstream in("cmap.in");
ofstream out("cmap.out");
pair<int, int> v[100001];
double dist_calc(int x1, int x2, int y1, int y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double dist_pair(unsigned int x, unsigned int y) {
return dist_calc(v[x].x, v[y].x, v[x].y, v[y].y);
}
double div_et_imp(unsigned int st, unsigned int fin) {
if (fin - st <= 3) {
double d = dist_pair(0, 1);
if (fin - st == 3) {
d = min(d, dist_pair(1, 2));
d = min(d, dist_pair(0, 2));
}
return d;
}
unsigned int med = st + (fin - st) / 2;
double d = min(div_et_imp(st, med), div_et_imp(med, fin));
vector <pair<int, int>> p;
for (unsigned int i = st; i < fin; i ++) {
// if (abs(med - v[i].x) <= d)
p.emplace_back(v[i].y, v[i].x);
}
sort(p.begin(), p.end());
for (unsigned int i = 0; i < p.size(); i ++) {
for (unsigned int j = i + 1; j < i + 8 && j < p.size(); j ++) {
d = min(d, dist_calc(p[i].x, p[j].x, p[i].y, p[j].y));
}
}
return d;
}
int main() {
int n;
in >> n;
for (unsigned int i = 0; i < n; i ++) {
in >> v[i].x >> v[i].y;
}
sort(v, v + n);
out << fixed << setprecision(6) << div_et_imp(0, n);
return 0;
}