Cod sursa(job #1026770)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 11 noiembrie 2013 23:13:54
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

using namespace std;

const int MaxArraySize = 100001;
const long long Inf = 1LL << 61;

long long n;
double ans;
pair<long long, long long> vec[MaxArraySize], x[MaxArraySize], y[MaxArraySize];

double dist(pair<long long, long long> a, pair<long long, long long> b) {
    return sqrt(1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second));
}

long long modul(long long val) {
    if (val < 0)
        return -val;
    return val;
}

double dive_et_imp(int st, int dr) {

    if (st >= dr - 1)
        return Inf;

    if (dr - st == 2) {
        if (y[st] > y[st + 1])
            swap(y[st], y[st + 1]);
        return dist(x[st], x[st + 1]);
    }

    long long mij, i, j, m = -1;
    double sol;

    mij = st + (dr - st) / 2;
    sol = min(dive_et_imp(st, mij), dive_et_imp(mij, dr));

    sort(y + st, y + dr);

    for (i = st; i < dr; ++i)
        if (sol >= modul(y[i].second - x[mij].first))
            vec[++m] = y[i];

    for (i = 0; i < m - 1; ++i) {
        for (j = i + 1; j < m && j - i < 8; ++j)
            sol = min(sol, dist(vec[i], vec[j]));
    }

    return sol;
}

int main() {

    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);

    int i;

    scanf("%lld", &n);

    for (i = 0; i < n; ++i)
        scanf("%lld %lld", &x[i].first, &x[i].second);

    sort(x, x + n);

    for (i = 0; i < n; ++i)
        y[i] = make_pair(x[i].second, x[i].first);

    ans = dive_et_imp(0, n);

    printf("%lf", ans);

    return 0;
}