Cod sursa(job #2073224)

Utilizator CobuzIonutCobuz Ionut-Alexandru CobuzIonut Data 22 noiembrie 2017 20:49:24
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 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(pair<int,int> a, pair<int,int>b)
{
    return a.Y < b.Y;
}

bool cmpX(pair<int,int> a, 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 dist = min(DI(st,m,pY),DI(m+1,dr,pY));
    int delta = (int)(ceil(sqrt(dist)));

    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) <= delta)
            z.push_back(pY[i]);
    ///sort(verif.begin(),verif.end(),cmp);

    for(unsigned i = 0; i < z.size(); i++)
        for(unsigned j = i+1;j< z.size() && z[j].Y - z[i].Y <= delta; j++)
            dist = min(dist, calculDist(z[i],z[j]));
    return dist;


}

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;

}