Cod sursa(job #1150995)

Utilizator manutrutaEmanuel Truta manutruta Data 23 martie 2014 19:41:37
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>

using namespace std;
typedef long long LL;

#define MAXN 100005
#define INF 4e18

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

vector< pair <LL, LL> > V(MAXN), X, Y;

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

LL go(int st, int dr, vector < pair <LL, LL> > &X, vector< pair <LL, LL> > &Y) {
    if (st >= dr - 1)
        return INF;
    else if (dr - st == 2) {
        if (Y[st] > Y[st + 1])
            swap(Y[st], Y[st + 1]);
        return dist(X[st], X[st + 1]);
    }
    int mid = (st + dr) / 2;
    LL best = min(go(st, mid, X, Y), go(mid + 1, dr, X, Y));

    sort(Y.begin() + st, Y.begin() + dr);

    int v_size = 0;
    for (int i = st; i < dr; ++ i) if (abs(Y[i].second - X[mid].first) <= best)
        V[v_size++] = Y[i];
    for (int i = 0; i < v_size - 1; ++ i) {
        for (int j = i + 1; j < v_size && j - i < 8; ++ j)
            best = min(best, dist(V[i], V[j]));
    }
    return best;
}

int main(void) {
    int n;
    f >> n;

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

    sort(X.begin(), X.end());
    for (int i = 0; i < (int) X.size(); ++ i)
        Y[i] = make_pair(X[i].second, X[i].first);

    g << fixed << setprecision(6) << sqrt(go(0, (int)X.size(), X, Y)) << "\n";

    f.close();
    g.close();
    return 0;
}