Cod sursa(job #3321618)

Utilizator rares89_Dumitriu Rares rares89_ Data 10 noiembrie 2025 15:46:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#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;
}