Cod sursa(job #2486381)

Utilizator mirunazMiruna Zavelca mirunaz Data 2 noiembrie 2019 19:44:46
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#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) {
    double d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return sqrt(d);
}

double dist_pair(int x, int y) {
    return dist_calc(v[x].x, v[y].x, v[x].y, v[y].y);
}

double div_et_imp(int st, 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;
    }

    int med = (st + fin) / 2;
    double d = min(div_et_imp(st, med), div_et_imp(med + 1, fin));
    vector <pair<int, int>> p;
    for (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 (int i = 0; i < p.size(); i ++) {
        for (int j = i + 1; j < i + 8 && j < p.size(); j ++) {
            d = min(d, dist_pair(i, j));
        }
    }
    return d;
}

int main() {
    int n;
    in >> n;
    for (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;
}