Cod sursa(job #2377728)

Utilizator vladm98Munteanu Vlad vladm98 Data 10 martie 2019 23:16:00
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-10;

double minimum (double a, double b) {
    if (a + eps <= b) return a;
    return b;
}

double sq (double x) {
    return x * x;
}

double getDistance (pair <double, double> A, pair <double, double> B) {
    return sqrt (sq(A.first - B.first) + sq(A.second - B.second));
}

double getDistance (vector <pair <double, double>> &points) {
    if (points.size() <= 3) {
        for (auto &x : points) {
            swap (x.first, x.second);
        }
        sort (points.begin(), points.end());
        for (auto &x : points) {
            swap (x.first, x.second);
        }
        double minim = 1e15;
        for (int i = 0; i < points.size(); ++i) {
            for (int j = i + 1; j < points.size(); ++j) {
                minim = minimum(minim, getDistance(points[i], points[j]));
            }
        }
        return minim;
    }
    vector <pair <double, double>> left, right;
    int middle = points.size() / 2;
    for (int i = 0; i <= middle; ++i) {
        left.push_back(points[i]);
    }
    for (int j = middle + 1; j < points.size(); ++j) {
        right.push_back(points[j]);
    }
    double minim = getDistance(left);
    minim = minimum (minim, getDistance(right));
    points.clear();
    reverse(left.begin(), left.end());
    reverse(right.begin(), right.end());
    while (left.size() || right.size()) {
        if (left.empty() || (right.size() and right.back().second + eps <= left.back().second)) {
            points.push_back(right.back());
            right.pop_back();
        }
        else {
            points.push_back(left.back());
            left.pop_back();
        }
    }
    for (int i = 0; i < points.size(); ++i) {
        for (int j = i + 1; j < min((int)points.size(), i + 8); ++j) {
            minim = minimum(minim, getDistance(points[i], points[j]));
        }
    }
    return minim;
}

int main() {
    ifstream fin ("cmap.in");
    ofstream fout ("cmap.out");
    vector <pair <double, double>> points;
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        double x, y;
        fin >> x >> y;
        points.emplace_back(x, y);
    }
    sort (points.begin(), points.end());
    fout << setprecision(7) << fixed << getDistance(points);
    return 0;
}