Cod sursa(job #1535014)

Utilizator adi_ispas95FMI - Adrian Ispas adi_ispas95 Data 24 noiembrie 2015 11:09:46
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;

const int MAX_N = 100005;
const long long int INF = 4e18;

double distanta(int xa, int ya, int xb, int yb){
    return sqrt((xa-xb) * (xa-xb) + (ya-yb)*(ya-yb));
}

vector <pair<long long int, long long int> > puncte(MAX_N), X, Y;

double cauta(int st, int dr, vector<pair<long long int, long long int> >& X, vector<pair<long long int, long long int> >& 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 distanta(X[st].first, X[st].second, X[st + 1].first, X[st + 1].second);
    }
    int mid = (st + dr) / 2;
    double best = min(cauta(st, mid, X, Y), cauta(mid, 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)
        puncte[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, distanta(puncte[i].first, puncte[i].second, puncte[j].first, puncte[j].second));
    }
    return best;

    return 0;
}

int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");

    int n;

    in >> n;

    X.resize(n), Y.resize(n);

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

    sort(X.begin(), X.end());

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

    out << setprecision(8) << cauta(0,X.size(),X,Y);

    return 0;
}