Cod sursa(job #2490832)

Utilizator alexburdescuBurdescu Alexandru alexburdescu Data 11 noiembrie 2019 00:52:18
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include<bits/stdc++.h>

using namespace std;

int const N = 100010;

pair<double,double>puncte[N];
pair<double,double>vec[N];
int n;


double dist( pair<double,double> A,pair<double,double>B)
{
    return pow(B.first - A.first,2)+ pow(B.second - A.second,2);
}

double divide(int st, int dr)
{
    if(st == dr)
        return INT_MAX;
    if(st == dr - 1)
        return dist(puncte[st], puncte[dr]);

    int mij = (st + dr)/2, k = 0;
    double x = divide(st, mij);
    double y = divide(mij + 1, dr);
    double result = min(x, y);

    for(int i = st; i <= dr; i++)
        if(abs(puncte[i].first - puncte[mij].first) < result)
            vec[++k] = {puncte[i].second, puncte[i].first};

    sort(vec + 1, vec + k + 1);

    for(int i = 1; i < k; i++)
        for(int j = i + 1; j <= k && j <= i + 8; j++)
            result = min(result, dist(vec[i], vec[j]));

    return result;
}


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


    fin >> n;
    int x,y;
    for(int i=0; i<n; i++)
    {
        fin >> x >> y;
        puncte[i] = make_pair(x, y);
    }

    sort(puncte, puncte+n);

    fout << fixed << setprecision(6) << sqrt(divide(0, n-1)) << "\n";

    fin.close();
    fout.close();

    return 0;
}