Cod sursa(job #2321396)

Utilizator TooHappyMarchitan Teodor TooHappy Data 16 ianuarie 2019 00:16:06
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

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

// X - vector sortat crescator dupa abscisa
// Y - vector sortat crescator dupa ordonata

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

long 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));
}

long double distMin(const vector< pair< int, int > > &X, const vector< pair< int, int > > &Y, int left, int right) {
    if (right - left + 1 == 2) {
        return dist(X[left], X[right]);
    }
    
    if (left == right) {
        return 1e9;
    }

    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);
        }
    }

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

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

    long double d3 = 1e9;
    for (int i = 0; i < (int)LY.size(); ++i) {
        for (int j = i + 1; j < i + 7; ++j) {
            if (j < (int)LY.size()) {
                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);

    int n; 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;
    });

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

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

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

    return 0;
}