Cod sursa(job #2073255)

Utilizator CobuzIonutCobuz Ionut-Alexandru CobuzIonut Data 22 noiembrie 2017 21:15:49
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>


using namespace std;

#define X first
#define Y second

vector <pair<int, int>> P;
int n;

double calculDist(pair<int, int> a, pair<int, int> b)
{
    double x = a.X - b.X;
    double y = a.Y - b.Y;
    double d;

    d = pow(x,2) + pow(y,2);
    return d;
}

bool cmpY(const pair<int,int>& a, const pair<int,int> &b)
{
    return a.Y < b.Y;
}

bool cmpX(const pair<int,int>& a, const pair<int, int> &b)
{
    return a.X < b.X;
}

double DI(int st, int dr, vector<pair<int,int>> &pY)
{
    if(dr - st == 1)
        return 4e18;
    if(dr - st == 2)
    {
       if(pY[st].Y > pY[st+1].Y)
            swap(pY[st], pY[st+1]);
       return calculDist(P[0],P[1]);
    }

    int m = (st + dr)/2,i,j;
    double distSt = DI(st,m,pY);
    double distDr = DI(m,dr,pY);
    double distRecursie = min(distSt, distDr);

    vector<pair<int,int>> verif(dr - st);
    merge(pY.begin() + st, pY.begin() + m, pY.begin() + m, pY.begin() + dr, verif.begin(), cmpY);
    copy(verif.begin(), verif.begin() + (dr - st), pY.begin() + st);

    vector<pair<int,int>> z;

    for(i = st; i <  dr; i++)
        if(abs(pY[i].X - P[m].X) <= distRecursie)
            z.push_back(pY[i]);
    ///sort(verif.begin(),verif.end(),cmp);
    double distFinala = distRecursie;
    for(int i = 0; i < z.size(); i++)
        for(int j = i+1;j< z.size() && z[j].Y - z[i].Y <= distRecursie; j++)
            {
                double dC = calculDist(z[i],z[j]);
                if(dC < distFinala)
                    distFinala = dC;
            }

    return distFinala;


}

int main()
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int x,y,i;
    fin>>n;

    for(i = 0; i < n; i++)
    {
        fin>>x>>y;
        P.push_back({x,y});
    }

    sort(P.begin(),P.end(),cmpX);

    vector<pair <int,int>> pY = P;


    fout<<fixed<<setprecision(6)<<sqrt(DI(0,P.size(),pY))<<"\n";
    fin.close();
    fout.close();
    return 0;

}