Cod sursa(job #2321337)

Utilizator TooHappyMarchitan Teodor TooHappy Data 15 ianuarie 2019 23:15:55
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("cmap.in");
ofstream out("cmap.out");

// X - vector sortat crescator dupa absica
// Y - vector sortat crescator dupa orodnata

int n;
vector< pair< int, int > > X, Y;

double dist(const pair< int, int > &a, const pair< int, int > &b) {
    return (sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)));
}

double distMin(const vector< pair< int, int > > &X, const vector< pair< int, int > > &Y, int left, int right) {
    if (right - left + 1 < 4) {
        double ans = 1e9;

        for (int i = 0; i < (int)X.size(); ++i) {
            for (int j = i + 1; j < (int)X.size(); ++j) {
                ans = min(ans, dist(X[i], X[j]));
            }
        }

        return ans;
    } else {
        int mid = (left + right) / 2;

        vector< pair< int, int > > leftY, rightY;
        for (auto it: Y) {
            if (it.first <= X[mid].first) {
                leftY.push_back(it);
            } else {
                rightY.push_back(it);
            }
        }

        double d1 = distMin(X, leftY, left, mid);
        double d2 = distMin(X, rightY, mid + 1, right);
        double d = min(d1, d2);

        vector< pair< int, int > > LY;
        for (auto it: Y) {
            if (X[mid].first - it.first < d) {
                LY.push_back(it);
            }
        }

        double d3 = 1e9;
        for (int i = 0; i < (int)LY.size(); ++i) {
            for (int j = i + 1; j < (int)LY.size(); ++j) {
                d3 = min(d3, dist(LY[i], LY[j]));
            }
        }

        return min(d, d3);
    }
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    in >> n;

    X.resize(n); Y.resize(n);
    for (int i = 0; i < n; ++i) {
        in >> X[i].first >> X[i].second;
        Y[i] = X[i];
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end(), [&](const pair< int, int > &a, const pair< int, int > &b) {
        if (a.second == b.second) {
            return a.first < b.first;
        }
        return a.second < b.second;
    });

    double ans = distMin(X, Y, 0, n -1);

    out << fixed << setprecision(6) << ans << "\n";

    in.close(); out.close();

    return 0;
}