Cod sursa(job #2472721)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 12 octombrie 2019 18:50:53
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 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], x[100001];

bool comp(pair<double, double> a, pair<double, double> b)
{
    if(a.first > b.first)
        return 0;
    return 1;
}

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)
        return min(distance(v[l], v[l+1]), distance(v[l+1], v[r]));

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

    int sze = 0;
    for(int i = l; i < r; i++)
        if(v[i].second - v[mid].first <= best)
            x[sze++] = v[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, comp);

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

    return 0;
}