Cod sursa(job #2492668)

Utilizator cosmin.stefan952Curcan Stefan Cosmin cosmin.stefan952 Data 15 noiembrie 2019 09:32:44
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <vector>
#include <utility>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");

struct Punct{

    int first, second;

};

int dist(Punct A, Punct B){

    int d= (B.first - A.first) * (B.first - A.first) + (B.second - A.second) * (B.second - A.second);
    return d;

}

bool compx(Punct A, Punct B){
    if(A.first != B.first)
        return A.first < B.first;
    return A.second < B.second;
}

bool compy(Punct A, Punct B){
    if(A.second != B.second)
        return A.second < B.second;
    return A.first < B.first;
}


int dist_min(vector<Punct>points, int stg, int drp){

    if(drp - stg +1 == 3){
        return min( dist(points[stg], points[stg+1]), min(dist(points[stg], points[drp]), dist(points[stg+1], points[drp])));
    }
    if(drp - stg +1 == 2){
        return dist(points[stg], points[drp]);
    }

    int  mid =  (stg + drp) / 2;

    int ds, dd, d;

    ds = dist_min(points, stg, mid);
    dd = dist_min(points, mid+1, drp);

    d = min(ds, dd);

    double x = sqrt(d);

    vector<Punct> y;

    for(int i = stg; i<=drp; i++)
        if(abs(points[mid].first - points[i].first) <= x)
            y.push_back(points[i]);

    sort(y.begin(), y.end(), compy);

    for(unsigned int i=0; i<y.size(); i++)
        for(unsigned int j= i+1; j<y.size() && j<=i+7; j++){
            d = min(dist(y[i], y[j]), d);
        }

     return d;
}


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

    vector<Punct>points;
    for(int i=0; i<n; i++)
    {
        Punct p;
        f>>p.first>>p.second;
        points.push_back(p);
    }

    sort(points.begin(), points.end(), compx);

    g << fixed << setprecision(6)<< sqrt(dist_min(points, 0, n-1));
    return 0;
}