Cod sursa(job #2489784)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 9 noiembrie 2019 11:49:50
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <cmath>
#include <iomanip>
#define MAX 2000000000

using namespace std;

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

pair<double, double> v[100001], w[100001], x[100001];

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

double result(int l, int r)
{
    if(l >= r-1)
        return MAX;

    if(l == r-2)
    {
        if (w[l] > w[l + 1])
            swap(w[l], w[l + 1]);
        return distance(v[l], v[l + 1]);
    }

    int mid = (l+r)/2;
    double best = min(result(l, mid), result(mid+1, r));

    merge(w+l, w+mid, w+mid, w+r, x);
    copy(x, x+(r-l), w+l);

    int sze = 0;
    for(int i = l; i < r; i++)
        if(abs(w[i].second - v[mid].first) <= best)
            x[sze++] = w[i];

    for(int i = 0; i < sze-1; i++)
        for (int j = i + 1; j < sze && j - i < 8; j++)
            best = min(best, distance(x[i], x[j]));

    return best;
}

int main()
{
    int n;
    in >> n;

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

    sort(v, v+n);
    for(int i = 0; i < n; i++)
    {
        w[i].first = v[i].first;
        w[i].second = v[i].second;
    }

    out << setprecision(8) << result(0, n-1);

    return 0;
}