Cod sursa(job #2073241)

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


using namespace std;

#define X first
#define Y second

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

long long calculDist(pair<int, int> a, pair<int, int> b)
{
    return (long long) (a.X-b.X) * (a.X-b.X)+ (long long)(a.Y - b.Y) * (a.Y - b.Y);
}

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;
}

long long DI(int st, int dr, vector<pair<int,int>> &pY)
{
    if(dr - st == 1)
        return 4e18;
    else 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;
    long long distSt = DI(st,m,pY);
    long long distDr = DI(m,dr,pY);
    long long 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);
    long long 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++)
            {
                long long 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,n-1,pY));
    fin.close();
    fout.close();
    return 0;

}